Härte von FPT-Problemen

Vertex Cover kann einfach auf Independent Set reduziert werden und umgekehrt.

Im Kontext der parametrisierten Komplexität ist die unabhängige Menge jedoch schwieriger als die Vertex-Abdeckung. Für Vertex Cover existiert ein Kernel mit Vertices, aber Independent Set ist W 1 hard.$2k$

Wie verändert sich die Natur von Independent Set im Kontext von FPT und warum?

Hauptidee der Antwort: Wenn wir eine Instanz eines parametrisierten unabhängigen Satzes auf eine parametrisierte Vertex-Abdeckung reduzieren, hängt der Parameter, den wir erhalten, von der Größe des Diagramms ab und hängt nicht nur vom Eingabeparameter ab. Nun zu etwas mehr Details.

Wie Sie wissen, liegt ein parametrisiertes Problem in (einheitlicher) FPT vor, wenn es einen Algorithmus gibt, der in der Zeit f ( k ) | entscheidet, ob eine Eingabe ( x , k ) in Q enthalten ist x | O ( 1 ) für eine Funktion f .$Q$$(x,k)$$Q$$f(k) |x|^{O(1)}$$f$

Da Sie entscheiden können, ob ein Graph eine Scheitelpunktabdeckung der Größe k hat, indem Sie eine Kante auswählen und verzweigen, welcher der beiden Endpunkte in die Scheitelpunktabdeckung eingefügt werden soll, geht diese Verzweigung nur k tief (andernfalls haben Sie mehr als k eingefügt) Ecken in der Abdeckung) und läuft leicht in der Zeit O ( 2 k n 2 ) ; deshalb ist k- Vertex Cover in FPT.$G$$k$$k$$k$$O(2^k n^2)$$k$

Angenommen, wir möchten versuchen, diesen Algorithmus zu verwenden, um zu zeigen, dass sich der parametrisierte unabhängige Satz in FPT befindet. nehmen wir einen Graphen gegeben auf n Ecken und wollen , um zu entscheiden , ob es eine unabhängige Menge von Größe hat l . Dies ist äquivalent zu der Frage , ob G eine Knotenüberdeckung der Größe hat n - l . Wir verwenden also unseren obigen Algorithmus, um die Antwort in O ( 2 n - ℓ n 2 ) zu berechnen . Für unseren FPT-Algorithmus hängt die Exponentialfunktion in der Laufzeit möglicherweise von dem Parameter ab, der ℓ ist, sie hängt jedoch möglicherweise NICHT von der Größe der Eingabe ab, die $G$$n$$\ell$$G$$n - \ell$$O(2^{n - \ell} n^2)$$\ell$$n$; Der von uns skizzierte Ansatz verwendet jedoch das Zeitexponential in und ist daher kein FPT-Parameter in Bezug auf den Parameter ℓ . Aus diesem Grund bedeutet die Tatsache, dass sich Vertex Cover in FPT befindet, nicht, dass sich Independent Set in FPT befindet.$n - \ell$$\ell$

Ich würde nicht sagen, dass sich die Art des Problems ändert, was auch immer das bedeuten soll. Alles, was sich ändert, ist der Parameter, dh die Art und Weise, wie Sie die Schwierigkeit des Problems messen.

Graphen mit einer Scheitelpunktabdeckung von höchstens sind so strukturiert, dass es möglich ist, sie effizient zu verkleinern: Wir können gierig eine maximale Übereinstimmung von höchstens k finden, und der Rest des Graphen ist mindestens eine unabhängige Menge von Größen n - 2 k . Mit Reduktionsregeln wie der Kronenreduktion kann die Anzahl der Eckpunkte auf maximal 2 k reduziert werden .$k$$k$$n-2k$$2k$

Auf der anderen Seite scheinen Graphen, die Scheitelpunktabdeckungen mit einer Größe von höchstens (oder äquivalent dazu, maximale Unabhängige haben eine Größe von mindestens k ), keine so einfache Struktur zu haben. Wie Sie bereits betont haben, kann dies präzisiert werden: Durch ihre Struktur können wir jedes W [ 1 ] -Problem codieren .$n-k$$k$$W[1]$

Das Folgende mag einen Anhaltspunkt für den Unterschied geben. Eine Untergruppe von Vertices S ist genau dann eine Vertexbedeckung von G = (V, E), wenn VS eine unabhängige Menge ist. Wenn also MVC die Größe einer minimalen Vertexbedeckung hat, ist MIS = | V | -MVC die Größe von die maximale unabhängige Menge. Ein mit X parametrisierter FPT-Algorithmus ermöglicht eine exponentielle Laufzeit als Funktion von X. Ein Zufallsgraph auf n Eckpunkten mit einer Kantenwahrscheinlichkeit von der Hälfte hat mit hoher Wahrscheinlichkeit eine MIS von etwa 2 logn und eine MVC von etwa n-2 logn. Zumindest für diese Graphen lässt ein von MVC parametrisierter FPT-Algorithmus einfach viel mehr Zeit als ein von MIS parametrisierter.

Auch wenn ich den Aussagen anderer zustimme, ist es für mich hilfreich, das Problem als Erkennungsproblem neu zu fassen: "Gehört das Eingabediagramm zu der Familie der Diagramme, deren Scheitelpunktabdeckung höchstens k beträgt?" / "Gehört das Eingabediagramm zu der Familie von Diagrammen, für die unabhängig mindestens k festgelegt wurde?"

Intuitiv sollte eine eingeschränktere Familie von Diagrammen leichter zu erkennen sein als eine umfassendere, allgemeinere. Die Familie der Scheitelpunktabdeckungsgraphen ist höchstens k sehr eingeschränkt. Tatsächlich kann jeder dieser Graphen mit nur Bits beschrieben werden, was viel weniger ist als die üblichen benötigten O ( n 2 ) Bits unter der Annahme, dass k signifikant kleiner als n ist. Die Familie der unabhängigen Graphen mit mindestens k ist dagegen sehr umfangreich: Jeder Graph kann bearbeitet werden, indem höchstens k 2 Kanten entfernt werden.$O(k^2+2^k\log n)$$O(n^2)$$k^2$

Für mich ist dies eine intuitive Erklärung, warum ich erwarten würde, dass es einfacher ist, kleine Scheitelpunkte als kleine unabhängige Mengen zu erkennen. Natürlich sollte es offensichtlich sein, dass die obigen Überlegungen bei weitem kein formales Argument sind, und ich denke, dass der überzeugendste Beweis dafür, dass es tatsächlich schwieriger ist, eine unabhängige Menge der Größe k zu erkennen, genau die W-Härte von independent ist einstellen!

Dies ist eine sehr indirekte Antwort, die Ihr Anliegen möglicherweise nicht ganz anspricht. FPT und die W-Hierarchie hängen jedoch eng mit der Approximierbarkeit zusammen (FPT-Probleme haben häufig PTASs usw.). In diesem Zusammenhang ist zu beachten, dass für jeden Graphen VC = n - MIS ist und daher eine Näherung für VC keine Näherung für MIS ergibt. Aus diesem Grund benötigen Sie L-Reduktionen zur Approximation. Ich vermute, dass es auch für die parametrisierte Komplexität einen äquivalenten Begriff für die "kernerhaltende Reduzierung" gibt.