Komplexität beim Zählen der Anzahl der Kantenabdeckungen eines Diagramms

Eine Kantenabdeckung ist eine Teilmenge von Kanten eines Diagramms, sodass jeder Scheitelpunkt des Diagramms an mindestens eine Kante der Abdeckung angrenzt. Die folgenden beiden Papiere sagen , dass Zählflanke Abdeckungen ist #P -komplette: Eine einfache FPTAS für Zählflanke Covers und Generieren von Kantenabdeckungen von Pfadgraphen . Sofern ich nichts verpasst habe, bieten sie jedoch keine Referenz für diese Behauptung oder einen Beweis. (Referenz 3 der ersten Veröffentlichung schien vielversprechend, aber ich habe dort auch nicht gefunden, was ich wollte.)

Wo finde ich eine Referenz oder einen Beweis dafür, dass das Zählen der Anzahl der Kantenabdeckungen eines Diagramms # P-vollständig ist?

reference-request graph-algorithms counting-complexity proofs a3nm
quelle

Antworten:

Ich weiß nicht, wo dies zum ersten Mal bewiesen wurde, aber da EdgeCover einen Ausdruck als boolesches Domain-Holant-Problem hat, ist er in vielen Holant-Dichotomiesätzen enthalten.

EdgeCover ist im Dichotomiesatz in (1) enthalten. Satz 6.2 (in der Journalversion oder Satz 6.1 im Vorabdruck) zeigt, dass EdgeCover gegenüber planaren 3-regulären Diagrammen # P-schwer ist. Um dies zu sehen, lautet der Ausdruck für EdgeCover als Holant-Problem bei 3-regulären Diagrammen (oder ersetzen Sie durch mit 1 für das gleiche Problem über reguläre Graphen). Diese -Notation listet die Ausgabe einer symmetrischen Funktion auf $\operatorname{Holant}([0,1,1,1])$ $[0,1,1,1]$ $[0,1,\dotsc,1]$ $k$ $k$ $[0,1,1,1]$ in der Reihenfolge der Eingabe Hamming Gewicht. Für eine Teilmenge der gesetzten Kanten (die wir als 1 zugewiesen und die Komplementmenge als 0 zugewiesen betrachten) besteht die Einschränkung an jedem Scheitelpunkt darin, dass mindestens eine Kante 1 zugewiesen wird, was genau die Funktion ist . Für eine feste Teilmenge von Kanten ist ihr Gewicht das Produkt der Ausgaben von an jedem Scheitelpunkt. Wenn ein Scheitelpunkt nicht abgedeckt ist, trägt er den Faktor . Wenn alle Scheitelpunkte abgedeckt sind, tragen alle Scheitelpunkte einen Faktor von , sodass das Gewicht ebenfalls beträgt $[0,1,1,1]$ $[0,1,1,1]$ $0$ $1$ $1$ . Dann muss der Holant über jede mögliche Teilmenge von Kanten summieren und das Gewicht addieren, das jeder Teilmenge entspricht. Dieser Holant-Wert ist genau der gleiche, wenn wir jede Kante unterteilen und die Bedingung auferlegen, dass beide einfallenden Kanten für diese neuen Scheitelpunkte gleich sein müssen. Unter Verwendung der symmetrischen Funktionsnotation ist diese binäre Gleichheitsfunktion . Dieser Graph ist zweiteilig. Die Scheitelpunkte in einem Teil haben die Einschränkung , während die Scheitelpunkte im anderen Teil die Einschränkung . Der Ausdruck dafür als Holant-Problem lautet . Dann können Sie selbst die Zeile " " und die Spalte " " $[1,0,1]$ $[0,1,1,1]$ $[1,0,1]$ $\operatorname{Holant}([0,1,1,1]|[1,0,1])$ $[0,1,1,1]$ $[1,0,1]$ "der Tabelle in der Nähe des oben genannten Theorems enthält" H ", was bedeutet, dass das Problem # P-schwer ist, auch wenn der Eingabediagramm planar sein muss.

Randnotiz: Beachten Sie, dass Pinyan Lu sowohl Autor dieses Papiers als auch des ersten Papiers ist, das Sie zitieren. Ich vermute, dass sie implizit (1) zitierten, als in ihrem Artikel stand, dass das Zählen von Kantenabdeckungen ein # P-vollständiges Problem ist, selbst wenn wir die Eingabe auf 3 reguläre Diagramme beschränken. Sie haben wahrscheinlich nicht erwähnt, dass die Härte auch dann gilt, wenn sie weiter auf ebene Graphen beschränkt ist, da ihr FPTAS diese Einschränkung nicht benötigt.

Spätere Holant-Dichotomie-Theoreme, wie sie in (2,3) - Konferenz- und Zeitschriftenversionen desselben Werks - vorkommen, haben mehr bewiesen. Satz 1 (in beiden Versionen) besagt, dass EdgeCover über planaren regulären Graphen für # P-hart ist . Um dies zu sehen, müssen wir eine holographische Transformation anwenden. Wie oben beschrieben, lautet der Ausdruck für EdgeCover als Holant-Problem über regulären Graphen , wobei 1 enthält . Außerdem entspricht dies . Nun wenden wir eine holographische Transformation durch $k$ $k \ge 3$ $k$ $\operatorname{Holant}([0,1,\dotsc,1])$ $[0,1,\dotsc,1]$ $k$ $\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$ $T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$ (oder umgekehrt, abhängig von Ihrer Perspektive). Nach Valiant's Holant Theorem (4,5) ändert dies nichts an der Komplexität des Problems (tatsächlich sind beide Probleme dasselbe Problem, da sie sich auf die Ausgabe jeder Eingabe einigen ... nur der Ausdruck des Problems hat sich geändert ). Der alternative Ausdruck für dieses Problem lautet

Holant ([1, 0, 1] T^{\otimes 2} | (T^{- 1})^{\otimes k} [0, 1, \dots, 1]) = Holant ([2, e^{π i / k}, e^{2 π i / k}] | =_{k}),

$\operatorname{Holant}([1,0,1] T^{\otimes 2}|(T^{-1})^{\otimes k} [0,1,\dotsc,1]) = \operatorname{Holant}([2, e^{\pi i / k}, e^{2 \pi i / k}]|=_k),$ wobei die Gleichheitsfunktion für Eingänge ist. Um Theorem 1 anzuwenden, müssen wir auf normieren durch Teilen der ursprünglichen Funktion durch , was die Komplexität des Problems nicht ändert, da dieser Wert ungleich Null ist. Dann sind die Werte und in der Aussage des Theorems und . Für

=_{k}

$=_k$

k

$k$

[2, e^{π i / k}, e^{2 π i / k}]

$[2, e^{\pi i / k}, e^{2 \pi i / k}]$

[2 e^{- π i / k}, 1, e^{π i / k}]

$[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$

e^{π i / k}

$e^{\pi i / k}$

X

$X$

Y

$Y$

X = 2

$X = 2$

Y = - 2^{k} - 1

$Y = -2^k - 1$

k \geq 3

$k \ge 3$ kann man überprüfen, ob dieses Problem, also auch EdgeCover, über planaren regulären Graphen für # P-hart ist .

k

$k$

k \geq 3

$k \ge 3$

Randnotiz: Diesen Satz und Beweis kann man auch in der These von Michael Kowalczyk sehen .

Ich werde meine Literatursuche fortsetzen, um zu sehen, dass EdgeCover vor (1) als # P-schwer eingestuft wurde.

(1) Holographische Reduktion, Interpolation und Härte von Jin-Yi Cai, Pinyan Lu und Mingji Xia ( Zeitschrift , Preprint ).

(2) Eine Dichotomie für rechtwinklige Graphen mit -Vertex-Zuweisungen und reellen Kantenfunktionen $k$ $\{0,1\}$ von Jin-Yi Cai und Michael Kowalczyk.

(3) Partitionsfunktionen auf Regelgraphen mit -Vertex-Zuweisungen und reellen Kantenfunktionen $k$ $\{0,1\}$ von Jin-Yi Cai und Michael Kowalczyk.

(4) Holographische Algorithmen von Leslie G. Valiant

(5) Valiant's Holant Theorem und Matchgate Tensoren von Jin-Yi Cai und Vinay Choudhary

Tyson Williams
quelle

Wow, danke, dass du mich darauf hingewiesen hast und dir die Zeit genommen hast, den Wortschatz und die Verbindung zum Edge Cover zu erklären! Ich stimme Ihnen zu, dass (1) implizit beweist, dass EdgeCover hart ist (und selbst für 3-reguläre ebene Graphen hart ist). Ich bin auch daran interessiert zu wissen, ob jemand die # P-Härte von EdgeCover vor (1) bewiesen hat, obwohl ich bereits sehr froh bin, dass ich etwas zu zitieren habe, wenn ich dieses Ergebnis verwenden muss (was mein Hauptanliegen war, wenn ich nachfrage) ). Nochmals vielen Dank für Ihre Antwort!

03.03.2014

@Tyson Williams: Wenn Sie von einem 2-3-regulären Graphen ausgehen und die Knoten der Partition von Grad 2 zusammenziehen, erhalten Sie möglicherweise einen 3-regulären Multigraph , dh mit parallelen Kanten. Kann dies behoben werden, um die Härte in 3-regulären einfachen Diagrammen anzuzeigen? Allgemeiner könnte diese Frage für alle Ergebnisse zu Holant-Problemen gestellt werden. Daher habe ich hier eine neue Frage erstellt: cstheory.stackexchange.com/q/43912/38111 , da das Problem meines Erachtens nicht auf dieses bestimmte Problem beschränkt ist ( Zählkante) deckt). Ich würde mich freuen, wenn Sie einen Blick darauf

werfen

Ah ja. Gute Beobachtung. Ich kann mich momentan nicht erinnern, welche Ergebnisse für einfache Diagramme vorliegen.

Tyson Williams

@TysonWilliams: Danke für die Bestätigung und keine Sorge! In meiner Community bedeutet "Grafik" immer "einfache Grafik", sofern nicht anders angegeben. Daher hatte ich dies in der Frage nicht explizit angegeben.

09.

@TysonWilliams: Schließlich haben wir herausgefunden, wie ein Härteergebnis beim Zählen von Kantenabdeckungen für einfache Graphen (die 2-3 reguläre bipartite und planare Graphen sind) über holographische Mittel erhalten werden kann. Die Details sind in der neuesten Version meiner Antwort unten und in Anhang D von arxiv.org/abs/1703.03201 enthalten . Wir verwenden die Härte des Zählens von Scheitelabdeckungen für dreistufige zweigliedrige planare Graphen aus xia2006regular: Diese Graphen haben keine Selbstschleifen, wir unterteilen jede Kante, die parallele Kanten entfernt, und cai2008holographic erzeugt keine Probleme. (Was 3-reguläre Grafiken

betrifft,

Nach einigen weiteren Literaturrecherchen hat sich herausgestellt, dass die Komplexität des Zählens der Kantenabdeckungen in einem Diagramm in Anhang A.1 (Randpfad 2008) # P-vollständig ist . (Dies setzt willkürliche Graphen als Eingabe voraus, dh sie können dem Eingabegraphen keine Annahmen aufzwingen, außer dass sie beobachten, dass der minimale Grad willkürlich groß gemacht werden kann). (bordewich2008path deutet weiter darauf hin, dass das Ergebnis in bubley1997graph ohne Beweis behauptet wird.) Dieses Ergebnis geht denjenigen von Cai, Lu und Xia voraus, auf die in Tyson Williams 'Antwort als (1) verwiesen wird, und es stützt sich nicht auf die holographische Theorie.

Insbesondere beruht das Ergebnis auf der # P-Härte der Zählung unabhängiger Mengen in 3-regulären Graphen, die in der greenhill2000-Komplexität gezeigt sind (Verbesserung des analogen Ergebnisses für Graphen mit höchstens 4 Graden, die in der vadhan1997-Komplexität gezeigt sind), und beweist das Ergebnis unter Verwendung der Technik von bubley1997graph .

Ein stärkeres Ergebnis, nämlich die Härte der Zählung von Kantenabdeckungen in einem zweigeteilten Graphen mit höchstens vier Graden (was weiterhin voraussetzt, dass der Kantensatz in vier Übereinstimmungen unterteilt werden kann), wurde unabhängig in khanna2011queries, Anhang B.1, ebenfalls ohne holographische Hilfsmittel untersucht . Sie stützen sich auf die Härte der Zählung unabhängiger Mengen in 3-regulären zweigliedrigen Graphen (gezeigt in xia2006regular durch Verfeinerung der Interpolationsmethode von vadhan1997complexity) und wenden dann eine Verfeinerung der Technik von bordewich2008path an.

Ein noch stärkeres Ergebnis (Härte der Zählung von Kantenabdeckungen in einem zweigliedrigen 2-3-Regelgraphen, dh einem zweigliedrigen Graphen, bei dem alle Scheitelpunkte auf einer Seite Grad 2 und alle Scheitelpunkte auf der anderen Seite Grad 3 haben, der zusätzlich eben ist) kann gezeigt werden mit den Ergebnissen von xia2006regular und cai2008holographic. Die Erläuterungen dazu finden Sie in Anhang D der neuesten Version unseres PODS'17-Dokuments . In diesem Fall haben wir ziemlich sorgfältig geprüft, ob das Ergebnis für einfache Diagramme gilt, dh für Diagramme, die weder Selbstschleifen noch Mehrkanten aufweisen (siehe die Kommentare zu Tyson Williams 'Antwort).

Für die Härte planarer 3-regulärer Graphen wird in der Antwort von Tyson Williams ein Argument angegeben, aber es scheint, dass es Mehrkanten und Selbstschleifen in den Graphen zulässt.

Verweise:

bordewich2008path: Martin Dyer, Magnus Bordewich, Marek Karpinski, Pfadkopplung mit Stoppzeiten und Zählung unabhängiger Mengen und Farben in Hypergraphen , 2008.
bubley1997graph: Russ Bubley, Martin Dyer, Graphorientierungen ohne Senke und eine Annäherung für einen harten Fall von #SAT , 1997. Keine Open-Access-Version scheint online verfügbar zu sein. :-(
cai2008holographic: J. Cai, P. Lu, M. Xia, Holographische Reduktion, Interpolation und Härte , 2008
greenhill2000- Komplexität : Catherine Greenhill, Die Komplexität, Färbungen und unabhängige Mengen in spärlichen Diagrammen und Hypergraphen zu zählen , 2000
khanna2011queries: Sanjeev Khanna, Sudeepa Roy, Val Tannen, Abfragen mit Unterschied zu probabilistischen Datenbanken , 2011.
vadhan1997-Komplexität: Salil P. Vadhan, Die Komplexität des Zählens in spärlichen, regelmäßigen und planaren Graphen , 1997. Einige Ergebnisse sind wahrscheinlich ursprünglich in einer Dissertation erschienen, aber ich habe sie nicht überprüft.
xia2006regular: Mingji Xia, Wenbo Zhao, # 3-Regular Bipartite Planar Vertex Cover ist # P-Complete , 2006. Online scheint keine Open-Access-Version verfügbar zu sein. :-( Beachten Sie, dass der erste Autor auch ein Autor von (1) in der Antwort von Tyson Williams ist.

Haftungsausschluss: Ich habe mir diese Artikel nur oberflächlich angesehen und bin kein Experte auf diesem Gebiet. Daher kann es in meiner obigen Zusammenfassung zu Fehlern kommen.

Dank eines anonymen PODS'17-Schiedsrichters, der mich auf khanna2011-Anfragen hingewiesen hat, was mich dazu veranlasste, diese Antwort zu schreiben.

a3nm
quelle