Härte von FPT-Problemen

13

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?

Nikhil
quelle

Antworten:

9

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)Qf(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.GkkkO(2kn2)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 n istGnGnO(2nn2)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

Bart Jansen
quelle
Vielen Dank für alle Antworten. Im Zusammenhang mit der parametrisierten Komplexität verstehe ich die Idee, wenn ich versuche, die Härte der unabhängigen Menge zu untersuchen, wobei ich aus Vertex Cover schließe. Allerdings habe ich keine Erklärung für Independent Set gefunden, unabhängig vom Kontext der Vertex-Abdeckung? Gibt es etwas in der Struktur (oder der inhärenten Natur), ein unabhängiges Set zu finden, das es schwieriger macht?
Nikhil
Bart, warum gibt es keinen Parameter für den die Reduzierung wie gewünscht funktioniert? k
Raphael,
@Raphael: Könnten Sie Ihre Frage klären? Die einzigen Parameter, die in der Frage des OP "erlaubt" sind, sind die jeweiligen Lösungsgrößen. Wenn wir beliebige Parameter zulassen, gibt es viele, für die die Reduktion wie gewünscht funktioniert (wenn ich diesen Ausdruck richtig verstanden habe): Wenn wir zum Beispiel den Parameter für beide Probleme als "Größe der Vertex-Abdeckung mit minimaler Größe" beibehalten, dann beide sind FPT; MinVC nach Barts Argument und MaxIndSet nach demselben Argument und unter Verwendung der OP-Reduktion. Es ist nur , wenn wir darauf bestehen , dass MaxIndSet die Paramter sein seine Lösung Größe , dass das Problem W [1] -hard wird.
gphilip
Sie verstehen meine Frage perfekt! In diesem Sinne ist die Frage des OP schlecht gestellt: Es ist nur sinnvoll, über parametrisierte Komplexität für Paare von (nicht parametrisierten) Problemen und Parametern zu sprechen. Ich mental die Lücke mit einem „forall“ gefüllt, was bedeutet , dass ich Barts Antwort in der „für alle lesen “ Sinn, auch, und dachte , es war falsch / unvollständig. Daher meine Frage. Andere Antworten haben übrigens das gleiche Problem. Anscheinend füllt jeder außer mir die Lücke mit der kanonischen Wahl. k
Raphael
6

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 .kkn2k2k

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 .nkkW[1]

Holger
quelle
4

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.


quelle
4

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(k2+2klogn)O(n2)k2

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!

Michael Lampis
quelle
Wie ist die Entfernung von -Kanten genug, um einem Graphen eine unabhängige Menge von k Eckpunkten zu geben? Ich würde denken, du würdest ( kk2kKantenentfernungen, wenn Sie eine unabhängige Menge der Größekin einem vollständigen Diagramm aufnEckpunkten erhaltenmöchten. (k2)+k(nk1)kn
Bart Jansen
@Bart: Für eine unabhängige Menge von Eckpunkten müssen Sie nur sicherstellen, dass keine Kante zwischen diesen k Eckpunkten existiert , und es gibt höchstens k ( k - 1 ) k 2 Kanten in einem (einfachen) Teilgraphen der Ordnung k . kkk(k1)k2k
Mathieu Chapelle
3

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.

Suresh Venkat
quelle
Gibt es in FPT den Begriff "kernel-preserving reduction"?
Nikhil
Ich weiß nicht: daher die Anführungszeichen :). Ich warte auf die parametrisierten Komplexitätsexperten.
Suresh Venkat
2
Du hast es gerade gerufen! ;)
Raphael
4
PptpQ(x,k)P(x,k)QkkO(1)PptpQQPQP
O(21/ϵnk)O(n1/ϵ)