Das ODD EVEN DELTA-Problem

Sei ein Graph. Sei sei eine ganze Zahl. Sei die Anzahl der kanteninduzierten Teilgraphen von mit Eckpunkten und einer ungeraden Anzahl von Kanten. Sei die Anzahl der kanteninduzierten Teilgraphen von mit Eckpunkten und einer geraden Anzahl von Kanten. Lassen . Das ODD EVEN DELTA-Problem besteht darin , gegebenes berechnen $G = ( V, E )$ $k \leq |V|$ $O_k$ $G$ $k$ $E_k$ $G$ $k$ $\Delta_k = O_k - E_k$ $\Delta_k$ und . $G$ $k$

Fragen

Ist es möglich, in Polynomzeit zu berechnen ? Welches ist der bekannteste Algorithmus, um es zu berechnen? $\Delta_k$

Was ist, wenn 3-regulär ist? $G$

Was ist, wenn 3-regulär zweiteilig ist? $G$

Was ist, wenn 3-regulär zweigliedrig planar ist? $G$

ds.algorithms graph-theory graph-algorithms counting-complexity Giorgio Camerani
quelle

Was ist deine Motivation?

Tyson Williams

@TysonWilliams: Meine Motivation ist, dass wenn der 1. Teil der 1. Frage eine positive Antwort hat (auch nur für den zweigliedrigen 3-regulären planaren Fall), es einige interessante Konsequenzen geben würde, die einer weiteren Untersuchung bedürfen. Wenn der Algorithmus subexponentiell ist, hätte er immer noch einige Konsequenzen (weniger interessant, verdient aber mehr Erforschung).

Giorgio Camerani

Kannst du genauer sein? Was meinst du mit "einigen interessanten Konsequenzen"? Wie sind Sie überhaupt auf dieses Problem gestoßen?

Tyson Williams

@TysonWilliams: Können wir dieses Gespräch privat per E-Mail fortsetzen?

Giorgio Camerani

Antworten:

Das ODD EVEN DELTA-Problem ist # P-schwer, selbst bei 3-regulären zweigliedrigen planaren Graphen.

$\mathcal{C}$ $G$ $G$

| C | = 2^{| V |} - \sum_{k = 2}^{| V |} Δ_{k} \cdot 2^{| V | - k}

$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$

Das Zählen von Scheitelpunktabdeckungen ist # P-vollständig, selbst in 3-regulären zweigliedrigen planaren Graphen, und es kann mit einer linearen Anzahl von Aufrufen an ein ODD EVEN DELTA-Orakel durchgeführt werden.

Giorgio Camerani
quelle

AKTUALISIEREN:

$k = |V|$ $k$

Das Holant-Framework ist im Wesentlichen eine exponentielle Summe über überspannende Untergraphen (dh alle Scheitelpunkte sind im Untergraphen vorhanden, sodass sich die Summe über den Teilmengen von Kanten befindet). Im Gegensatz dazu handelt es sich in der aktuellen Version der Frage um kanteninduzierte Teilgraphen.

$|V|$

3-regelmäßige planare Graphen

$G$

Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) .

$\text{Pl-Holant}([1,0,-1]|[0,1,1,1]).$

Lassen Sie mich erklären, wie. Weitere Einzelheiten als unten angegeben finden Sie in diesem Dokument .

Der Holant ist eine Summe über (Boolesche) Zuordnungen zu Kanten. Auf den Eckpunkten befinden sich Einschränkungen, deren Eingaben die Zuordnungen zu ihren einfallenden Kanten sind. Für jede Zuordnung zu den Kanten nehmen wir das Produkt aller Scheitelpunktbeschränkungen.

Ihre Anforderung, dass es keine isolierten Scheitelpunkte gibt, ist die Einschränkung, die an einem bestimmten Scheitelpunkt nicht erfüllt ist, wenn keine seiner einfallenden Kanten ausgewählt ist, und erfüllt ist, wenn mindestens eine Kante ausgewählt ist. Diese symmetrische Einschränkung wird mit [0,1,1,1] bezeichnet, das 0 (dh unbefriedigt) ausgibt, wenn die Anzahl der Eingänge 1 0 ist (dh keine einfallenden Kanten im Untergraphen), und 1 (dh erfüllt) ausgibt, wenn die Zahl der Eingabe 1 ist 1, 2 oder 3 (dh 1, 2 oder 3 einfallende Kanten im Untergraphen).

$G$ $G$ $n$ $(-1)^n = 1$ $n$ $(-1)^n = -1$

Dieses zweiteilige Holant-Problem ist nach Satz 6.1 in diesem Artikel # P-schwer . Dieser Satz ist jedoch nicht am einfachsten anzuwenden. Beachten Sie stattdessen Folgendes.

$T = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix},$

\begin{aligned} Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) & = Pl-Holant ([1, 0, - 1] T^{\otimes 2} | (T^{- 1})^{\otimes 3} [0, 1, 1, 1]) \\ = Pl-Holant ([1, - 1, 0] | [1, 0, 0, 1]) . \end{aligned}

$\begin{align*} \text{Pl-Holant}([1,0,-1]|[0,1,1,1]) &= \text{Pl-Holant}([1,0,-1] T^{\otimes 2}|(T^{-1})^{\otimes 3}[0,1,1,1])\\ &= \text{Pl-Holant}([1,-1,0]|[1,0,0,1]). \end{align*}$

Dann ist es leicht zu erkennen, dass dieses Problem nach Satz 1.1 in diesem Artikel # P-schwer ist .

Beschränkung auf zweigeteilte Graphen

Genau wie bei Ihrer vorherigen Frage ist das gleiche Problem, das auf zweigeteilte Diagramme beschränkt ist, viel schwieriger zu behandeln, und ich glaube, es ist immer noch ein offenes Problem. Wir haben eine Vermutung bezüglich der nachvollziehbaren Fälle (und ich werde prüfen, ob Ihr Problem eines davon ist), aber ich denke, Ihr Problem ist immer noch # P-schwer, selbst wenn es auf zweigeteilte Graphen beschränkt ist.

Tyson Williams
quelle

Vielen Dank, dass Sie sich dieser Frage gewidmet haben und eine so ausführliche Antwort gegeben haben. Da ich mit dem Holant-Framework nicht vertraut bin, werde ich einige Zeit brauchen, um es zu analysieren und Ihre Argumentation vollständig zu verstoffwechseln (natürlich habe ich keinen Zweifel an seiner Richtigkeit, ich möchte nur jeden Schritt verstehen, nicht nur die Schlussfolgerung). . Was die Einschränkung der Zweiteiligkeit betrifft, wäre es wirklich schön, wenn Sie prüfen könnten, ob Ihre Vermutung über nachvollziehbare Fälle mein Problem umfasst.

Giorgio Camerani