Subexponentiell lösbare harte Graphprobleme

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 $2^{O(n^{1/2} \log n)}$ Laufzeit. Ein weiteres Beispiel ist das log-Clique-Problem, das in quasi-polynomialer Zeit ( $n^{O(\log n)}$ ) 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^{\Omega(n)}$ Zeit benötigen .

Übrigens kann das Max - Clique - Problem allgemein in Zeit wobeiNdie Größe der Eingabe ist.$2^{\tilde O(\sqrt 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|^2$$2^{O(|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 ($2^{\tilde O(\sqrt{|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öße≥k gibt.$2^{\tilde O(\sqrt{|V| + |E|})}$$G=(V,E)$$k$$\geq k$

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 $< k$$V'$$\geq k$$\geq k$$|V'|^k$$|E| \geq k\cdot |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\leq |V'|$$|E| \geq k^2/2$$|V'|^k$.$2^{O(\sqrt{|E|} \cdot \log |V|)}$

Da jeder planare Graph auf Ecken die Baumbreite O ( $n$alle Probleme, die inO∗lösbar sind$O(\sqrt{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 ( $O^*(2^{O(k)})$$k$für Graphen aufnEckpunkten. Beispiele sind Planar Independent Set und Planar Dominating Set, die natürlich NP-vollständig sind.$O^*(2^{O(\sqrt{n})})$$n$

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,\nu)$$(Q,\kappa)$

Theorem . ist in SUBEPT, wenn ( Q , κ ) in FPT ist.$(P,\nu)$$(Q,\kappa)$

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 kann$k$$k$$O(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.$2^{O(\sqrt{m}\log m)}$$k$$k$

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.

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)$2^{o(n)}$

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/\text{polylog } n$$n$

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 $n^{1-o(1)}$ Annäherung für Cliqueso gut wie Polynomialzeit-Algorithmen würde jemals tun.$n/\text{polylog } n$

Aber Näherung von $n/\text{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^{\Omega(n)}$$2^{\Omega(N^\epsilon)}$$N=n^{1/\epsilon}$$\epsilon$