Subexponentiell lösbare harte Graphprobleme

25

Angesichts der jüngsten Ergebnisse von Arora, Barak und Steurer, Subexponentielle Algorithmen für einzigartige Spiele und verwandte Probleme , interessiere ich mich für Graphprobleme , die subexponentielle Zeitalgorithmen haben, aber als nicht polynomiell lösbar gelten. Ein bekanntes Beispiel ist die Graphisomorphie subexponentiellen Algorithmus hat 2O(n1/2logn) Laufzeit. Ein weiteres Beispiel ist das log-Clique-Problem, das in quasi-polynomialer Zeit ( nO(logn) ) lösbar ist .

Ich suche interessante Beispiele und vorzugsweise einen Verweis auf Umfragen zu subexponentiellen Problemen mit harten Graphen (nicht unbedingt NP -vollständig). Gibt es auch NP -vollständige Graphprobleme mit subexponentiellen Zeitalgorithmen?

Impagliazzo, Paturi und Zane zeigten, dass die Exponentialzeithypothese impliziert, dass Clique, k-Colorability und Vertex Cover 2Ω(n) Zeit benötigen .

Mohammad Al-Turkistany
quelle
2
Der Vollständigkeit halber : log-CLIQUE = {(G,k)|G has n vertices, k=logn and G has a clique of size k}
MS Dousti

Antworten:

20

Übrigens kann das Max - Clique - Problem allgemein in Zeit wobeiNdie Größe der Eingabe ist.2O~(N)N

Dies ist trivial, wenn der Graph über eine Adjazenzmatrix dargestellt wird, denn dann ist , und eine Brute-Force-Suche dauert 2 O ( | V | ) .N=|V|22O(|V|)

Aber wir können dieselbe Grenze erhalten, auch wenn der Graph durch Adjazenzlisten dargestellt wird, und zwar über einen Algorithmus mit einer Laufzeit von . Um zu sehen, wie, lassen Sie uns eine2 ˜ O (2O~(|V|+|E|)-Zeitalgorithmus für das NP-Gesamtentscheidungsproblem, bei dem wir einen GraphenG=(V,E)undk erhaltenund wissen wollen, ob es eine Clique der Größek gibt.2O~(|V|+|E|)G=(V,E)kk

Der Algorithmus entfernt einfach alle Scheitelpunkte des Grades und die auf sie einfallenden Kanten und macht es dann erneut und so weiter, bis wir einen Scheitelpunkt-induzierten Untergraphen über einer Untergruppe V ' von Scheitelpunkten haben, die jeweils einen Grad k haben. oder mit einem leeren Diagramm. Im letzteren Fall wissen wir, dass keine Clique der Größe k existieren kann. Im ersteren Fall, tun wir eine Brute-Force-Methode in der Zeit läuft unrund | V ' | k . Beachten Sie, dass | E | k | V ' | / 2 und k <kVkk|V|k|E|k|V|/2, damit das | E | k 2 / 2 , und so eine Brute-Force-Methode inZeit läuft | V ' | k läuft gerade in der Zeit 2 O ( k|V||E|k2/2|V|k.2O(|E|log|V|)

Luca Trevisan
quelle
12
In der Tat argumentierten Impagliazzo, Paturi und Zane aus diesen Gründen, dass bei der Frage nach vs 22Ω(n)Komplexität o ( n ) nauf die Größe des Zeugeneinstellenmüssen (für den Sie einen Teil definieren müssen) das Problem). ImFallderk-Klasse hat der Zeuge die Größelog ( | V |2o(n)nkfür smallk, während Sie, wie Sie sagen, davon ausgehen können, dass wlog mindestensk| V| Kanten und die Eingabegröße ist viel größer als die Zeugengröße. log(|V|k)klog|V|kk|V|
Boaz Barak
22

Da jeder planare Graph auf Ecken die Baumbreite O ( nalle Probleme, die inOlösbar sind(O(n) Zeit für Graphen mit einer Baumbreite von höchstens ~ k(es gibtVIELEsolcher Probleme), haben Subexponentialzeitalgorithmen auf ebenen Graphen, indem ein Konstantfaktor berechnet wird Annäherung an die Baumbreite in Polynomzeit (z. B. durch Berechnung der Verzweigungsbreite mit dem Ratcatcher-Algorithmus) und anschließende Ausführung des Baumbreiten-Algorithmus, was zu Laufzeiten der Form O ( 2 O ( √) führtO(2O(k))kfür Graphen aufnEckpunkten. Beispiele sind Planar Independent Set und Planar Dominating Set, die natürlich NP-vollständig sind.O(2O(n))n

Bart Jansen
quelle
15

Es besteht eine enge Verbindung zwischen Unter exponentieller Zeit Lösbarkeit (SUBEPT) und festen Parameter Lenkbarkeit (FPT). Die Verbindung zwischen ihnen wird in dem folgenden Papier bereitgestellt.

Ein Isomorphismus zwischen subexponentieller und parametrisierter Komplexitätstheorie , Yijia Chen und Martin Grohe, 2006.

Kurz gesagt, sie führten einen Begriff ein, der als Miniaturisierungsabbildung bezeichnet wird und ein parametrisiertes Problem auf ein anderes parametrisiertes Problem ( Q , κ ) abbildet . Wenn wir ein normales Problem als ein Problem betrachten, das durch die Eingabegröße parametrisiert ist, haben wir den folgenden Zusammenhang. (Siehe Satz 16 in der Arbeit)(P,ν)(Q,κ)

Theorem . ist in SUBEPT, wenn ( Q , κ ) in FPT ist.(P,ν)(Q,κ)

Achten Sie auf die Definitionen hier. Normalerweise betrachten wir das Problem der Klasse als in k parametrisiert , so dass es keinen subexponentiellen Zeitalgorithmus gibt, für den eine Exponentialzeithypothese angenommen wird. Aber hier lassen wir das Problem durch die Eingangsgröße O ( m + n ) parametrisieren , so dass das Problem in 2 O ( √) gelöst werden kannkkO(m+n)ist ein subexponentieller Zeitalgorithmus. Und der Satz sagt uns, dass dask-Klassen-Problem ein fester Parameter ist, der unter der gewissen Verdrehung des Parametersknachvollziehbar ist, was vernünftig ist.2O(mlogm)kk

Im Allgemeinen können Probleme bei SUBEPT unter SERF-Reduktionen (subexponentielle Reduktionsfamilien) in Probleme bei FPT unter FPT-Reduktionen umgewandelt werden. (Theorem 20 in der Arbeit) Darüber hinaus sind die Verbindungen noch stärker, da sie einen Isomorphismus-Theorem zwischen einer ganzen Hierarchie von Problemen in der Exponential-Zeit-Komplexitätstheorie und der parametrisierten Komplexitätstheorie liefern. (Theorem 25 und 47) Obwohl der Isomorphismus nicht vollständig ist (es gibt einige fehlende Verbindungen zwischen ihnen), ist es immer noch schön, ein klares Bild über diese Probleme zu haben, und wir können subexponentielle Zeitalgorithmen über parametrisierte Komplexität untersuchen.

Weitere Informationen finden Sie in der Umfrage von Jörg Flum und Martin Grohe zusammen mit Jacobo Torán, dem Herausgeber der Komplexitätsspalte.

Hsien-Chih Chang 張顯 張顯
quelle
Ja. Übrigens haben Flum und Grohe die Umfrage geschrieben; Toran ist der Editor für Komplexitätsspalten.
Andy Drucker
@ Andy: Danke für die Korrektur. Ich werde den Artikel entsprechend modifizieren.
Hsien-Chih Chang 張顯 張顯
12

Ein anderes Beispiel ist das Cop and Robber-Spiel, das NP-hart ist, aber in der Zeit auf Graphen mit n Eckpunkten lösbar ist . BibTeX-Titelsatz in XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Verfolgung eines schnellen Räubers in einem Graphen. Theor. Comput. Sci. 411 (7-9): 1167-1181 (2010)2o(n)

XXYYXX
quelle
3
Hoppla, das mag beschämend sein, aber ich hatte lange Zeit geglaubt, dass -harte Probleme keine subexponentiellen Zeitalgorithmen haben, nur weil die Exponential Time Hypothese. :(NP
Hsien-Chih Chang 張顯 張顯
6
Keine Schande ... aber eine einfache Möglichkeit zu erkennen, dass dies nicht zutrifft, besteht darin, eine beliebige -harte Sprache L N P T I M E ( n k ) zu nehmen und dann eine 'gepolsterte' Version L 'zu bilden, in der Die 'Ja'-Instanzen haben die Form ( x , 1 | x | c ) mit x L für ein bestimmtes festes c > k . Dann L ' ist N PNPLNPTIME(nk)L(x,1|x|c)xLc>kLNP, hat aber einen deterministischen Algorithmus, der zeitlich im wesentlichen . 2nk/c
Andy Drucker
7

Der beste Näherungsalgorithmus für Clique liefert einen unglaublich schlechten Näherungsfaktor (man denke  daran, dass der Näherungsfaktor von n trivial ist).n/polylog nn

Es gibt Näherungsergebnisse für die Härte unter verschiedenen Härteannahmen, die nicht ganz übereinstimmen, aber dennoch eine Härte von . Persönlich glaube ich, dass n /n1o(1) Annäherung für Cliqueso gut wie Polynomialzeit-Algorithmen würde jemals tun.n/polylog n

Aber Näherung von n/polylog n für clique kann jedoch leicht in quasi-polynomialer Zeit erfolgen.


Ein NP-hartes Problem ist ein Problem, das eine Polynomzeitverkürzung von SAT aufweist. Selbst wenn SAT Zeit , kann dies zu Zeit 2 Ω ( N ϵ ) für das Problem führen, auf das wir reduzieren. Wenn letztere die Eingangsgröße N hat, kann es der Fall sein, dass N = n 1 / ϵ für eine kleine Konstante ϵ ist .2Ω(n)2Ω(Nϵ)N=n1/ϵϵ

Dana Moshkovitz
quelle