Zählung der Anzahl der Scheitelpunktabdeckungen: Wann ist es schwierig?

Man betrachte das # P-vollständige Problem des Zählens der Anzahl der Scheitelpunktabdeckungen eines gegebenen Graphen .$G = (V, E)$

Ich würde gerne wissen, ob es ein Ergebnis gibt, das zeigt, wie die Härte eines solchen Problems mit einem Parameter von variiert (zum Beispiel ).$G$$d = \frac{|E|}{|V|}$

Mein Gefühl ist , dass das Problem leichter sein sollte , sowohl wenn ist spärlich und wenn G ist dicht, während es schwer sein sollte , wenn G „in der Mitte“ ist. Ist das wirklich der Fall?$G$$G$$G$

Das #VC-Problem der Berechnung der Anzahl der Scheitelpunktabdeckungen eines gegebenen Graphen bleibt für 3-reguläre Graphen # P-schwer; siehe zum Beispiel [Greenhill, 2000].

Um zu zeigen , dass das #VC Problem für Graphen # P-hart bleibt mit höchstens $c\cdot n$ Kanten, wobei $n$ die Anzahl der Scheitelpunkte und $0<c<3/2$ , reduziert aus dem 3-Normalfall durch eine ausreichend große Zugabe unabhängige Menge (von linearer Größe). Die Anzahl der Scheitelpunktabdeckungen bleibt gleich, wenn Sie eine unabhängige Menge hinzufügen.

In ähnlicher Weise zu zeigen , dass das Problem für #VC Graphen # P-hart bleibt mit mindestens $c\cdot n^2$ Kanten, wobei $n$ die Anzahl der Scheitelpunkte und $0<c<1/2$ , von #VC zu reduzieren , indem eine ausreichend große Zugabe Clique-Komponente (von linearer Größe). Die Anzahl der Vertex-Covers wird mit $p+1$ multipliziert, wenn Sie einer Grafik eine Clique der Größe $p$ hinzufügen .

Catherine S. Greenhill: Die Komplexität, Färbungen und unabhängige Mengen in spärlichen Diagrammen und Hypergraphen zu zählen . Computational Complexity 9 (1): 52-72 (2000)

Nach Jaroslaws Antwort zeigten Luby und Vigoda als erste ein FPRAS für #IS unter einer Dichtebedingung (maximaler Grad 4, der meines Erachtens schwächer ist als Weitz 'Ergebnis), während Dyer, Frieze und Jerrum zeigten, dass es kein FPRAS für #IS gibt #IS wenn der maximale Grad des Graphen 25 ist, außer RP = NP.

Verweise:

Martin Dyer, Alan Frieze und Mark Jerrum. Zum Zählen unabhängiger Mengen in spärlichen Diagrammen. FOCS 1999.

Michael Luby und Eric Vigoda. Zählt ungefähr bis zu vier. STOC 1997.

Siehe auch das Vorlesungsskript von Jerrum, "Zählen, Abtasten und Integrieren: Algorithmen und Komplexität".

In Bezug auf die exponentielle zeitliche Komplexität sind allgemeine Instanzen und Instanzen mit konstantem Maximalgrad gleichermaßen schwierig: Das Sparsifikations-Lemma von Impagliazzo, Paturi, Zane (2002) zeigt, dass -variable Instanzen von d- Sat auf Instanzen von d- Sat reduziert werden können mit höchstens f ( d , ϵ ) ⋅ n Klauseln in der Zeit exp ( ϵ n ) . Wie in Zusammenarbeit mit Husfeldt und Wahlén festgestellt wurde, funktioniert das Sparsifikations-Lemma auch für die Zählversionen von d- Sat und insbesondere für den Fall des Zählens von $n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (entspricht dem Zählen unabhängiger Mengen und dem Zählen von Scheitelpunktabdeckungen).

Darüber hinaus kann das Zählen unabhängiger Mengen in einem Vertex-Graphen nicht in der Zeit exp ( o ( n ) ) durchgeführt werden, es sei denn, die Exponentialzeithypothese schlägt fehl. Dies ist eine noch unveröffentlichte Beobachtung, die in einem Vortrag während des Dagstuhl-Seminars Computational Counting angekündigt wurde .$n$$\exp(o(n))$

Set ist eine Vertex-Abdeckung, wenn sein Komplement eine unabhängige Menge ist, daher entspricht dieses Problem dem Zählen unabhängiger Mengen.

Die algebraische Zählung unabhängiger Mengen ist eine FPT für Graphen mit begrenzter begrenzter Cliquenbreite. Siehe zum Beispiel Courcelles "Ein multivariates Interlace-Polynom und seine Berechnung für Graphen mit begrenzter Cliquenbreite", wo sie eine Verallgemeinerung des Unabhängigkeitspolynoms berechnen. Addiert man die Unabhängigkeitspolynomkoeffizienten, so erhält man die Anzahl der unabhängigen Mengen.

Diagramme mit maximalem Grad 3 können eine unbegrenzte Clique-Breite haben.

Die numerische Zählung unabhängiger Mengen ist nachvollziehbar, wenn das Problem einen "Korrelationszerfall" aufweist. Dror Weitz ( STOC'06 ) gibt ein deterministisches FPTAS zum Zählen gewichteter unabhängiger Mengen auf Graphen mit maximalem Grad an$d$ wenn das gewicht $\lambda$ ist

_{(Quelle: yaroslavvb.com )}

Regelmäßige (ungewichtete) unabhängige Mengenzählung entspricht $\lambda=1$ Daher gibt sein Algorithmus FPTAS für die Anzahl der Scheitelpunktabdeckungen in Diagrammen mit maximalem Grad 5 an.

Sein Algorithmus basiert darauf, an jedem Scheitelpunkt einen selbstvermeidenden Gehbaum zu erstellen und diesen Baum in der Tiefe abzuschneiden $d$. Der Verzweigungsfaktor selbstvermeidender Gehbäume bestimmt die Reichweite von$\lambda$ für welche kleine tiefe $d$ ergibt eine gute Annäherung, und die obige Formel wird abgeleitet, indem der maximale Grad des Graphen zur oberen Grenze dieses Verzweigungsfaktors verwendet wird.