Komplexität beim Zählen von Übereinstimmungen in einem zweigeteilten Diagramm

8

Möglicherweise fehlt mir etwas Offensichtliches, aber ich kann keine Hinweise auf die Komplexität des Zählens von Übereinstimmungen (nicht perfekte Übereinstimmungen) in zweigeteilten Diagrammen finden. Hier ist das formale Problem:

  • Eingabe: ein zweigeteilter Graph mitE U × V.G=(U,V,E)EU×V
  • Ausgabe: Die Anzahl der Übereinstimmungen von , wobei eine Übereinstimmung eine Teilmenge so dass kein vorhanden ist , das an zwei Kanten von auftritt .Gv U V F.FEvUVF

Was ist die Komplexität dieses Problems? Ist es # P-schwer?

Es ist bekannt, dass das Zählen perfekter Übereinstimmungen auf zweigeteilten Graphen # P-schwer ist, und es ist bekannt, dass das Zählen von Übereinstimmungen beliebiger Graphen (oder sogar planarer 3-regulärer Graphen) in diesem Artikel # P-schwer ist , aber ich habe es nicht getan. Ich finde nichts über das Zählen nicht perfekter Übereinstimmungen in zweigeteilten Graphen.

a3nm
quelle
Es scheint ein Problem mit diesem Algorithmus zu geben. Es gibt Fälle im Ergebnis, in denen nicht alle Knoten von der linken oder rechten Seite in der 2sat-Lösung enthalten sind, sodass der exakte Zählalgorithmus nicht funktioniert. Kennt jemand einen Algorithmus für einzelne maximale bipartite Matching-Lösungen, der unter Verwendung einer Reduktion auf 2sat abgeleitet wurde?
user3700810

Antworten:

13

Das Problem des Zählens solcher "unvollständiger" Übereinstimmungen in zweigeteilten Graphen ist # P-vollständig.
Dies wurde von Les Valiant selbst auf Seite 415 des Papiers bewiesen

Leslie G. Valiant
Die Komplexität von Aufzählungs- und Zuverlässigkeitsproblemen
SIAM J. Comput., 8 (3), 410–421

Gamow
quelle
Sieht gut aus, danke! Ich weiß nicht, warum diese einfache Tatsache auf der Wikipedia-Seite (oder an anderer Stelle im Internet) nicht eindeutig angegeben wurde. Ich habe Wikipedia entsprechend verbessert: en.wikipedia.org/w/… Nochmals vielen Dank!
A3NM
0

Eine Woche in meinem Kurs über Komplexitätstheorie am College bestand unser einziges Hausaufgabenproblem darin, zu beweisen, dass # 2-SAT # P-vollständig war, indem wir von #BIPARTITE PERFECT MATCHING reduzierten. Niemand konnte es lösen, selbst wenn wir uns schließlich alle zusammenschlossen, um daran zu arbeiten.

In der nächsten Klasse war der Professor überrascht, wie schwierig wir alle es gefunden hatten, und legte seinen Beweis vor. Es war falsch. Glücklicherweise konnte ein intelligenter Cookie die richtige Reduzierung erzielen, was absolut verrückt und widerlich kompliziert war. Der Professor hat übrigens einen Turing Award :)

Obwohl ich und meine Klassenkameraden dieses Problem nicht lösen konnten, konnten wir das einfachere Problem der Reduzierung von #BIPARTITE MATCHING auf # 2-SAT lösen. Hier ist der Beweis, den ich vor einigen Jahren gefunden habe.

Satz. #BIPARTITE MATCHING # 2-SAT.p

Beweis . Sei eine Instanz von #BIPARTITE MATCHING. Die Partitionsmengen seien (also und ) .A = { a ii [ n ] } ,G=(V,E)| A | = n | B | = m

A={aii[n]},B={bii[m]}
|A|=n|B|=m

Nun reduzieren wir auf eine 2SAT-Formel , so dass jede erfüllende Zuordnung von eine Übereinstimmung von ist und umgekehrt. Zu Beginn erstellen Sie für jede Kante eine Variable . Die Idee ist, dass das Setzen der Variablen auf TRUE der Kante entspricht, die im Matching enthalten ist. Erstellen Sie für jeden Scheitelpunkt die 2SAT-Ausdrücke Damit erfüllt ist, muss bis auf höchstens eines von falsch sein. Um dies zu sehen, nehmen Sie beideφ φ G a i b jE x i jGφφGaibjExijxijaibjiA i x i j x i j x i k ( ¬ x i j¬ x i k ) A i B i C = n i = 1 A im i = 1 B.

Ai=j<k(¬xij¬xik),Bi:=j<k(¬xji¬xki)
Aixijxijund sind wahr. Dann ist falsch, ebenso wie . Gleiches gilt für . Wenn wir , haben wir, dass genau dann erfüllt ist, wenn jeder Scheitelpunkt in auf höchstens eine von uns gewählte Kante trifft, und somit Die Kanten bilden eine Übereinstimmung.xik(¬xij¬xik)AiBi C G.
C=i=1nAii=1mBi
CG
Gartenkopf
quelle
Ich denke, ich muss hier etwas vermissen. Dies scheint zu zeigen, dass eine beliebige Instanz von #BIPARTITE_MATCHING als Instanz von # 2-SAT codiert werden kann. Aber ich habe erwartet, dass Sie versuchen würden zu zeigen, dass eine beliebige Instanz von # 2-SAT als Instanz von #BIPARTITE_MATCHING codiert werden kann, nicht wahr?
mhum
Hoppla, du hast recht. Dies wurde von einem alten Hausaufgabenproblem gelöst und ich hatte die Frage nicht wirklich aufgeschrieben, sondern nur meine Antwort. Das Problem muss gewesen sein zu zeigen, dass # 2-SAT # P-vollständig war, in dem Wissen, dass # BIPARTITE-PERFECT-MATCHING # P-vollständig war. Ich werde es bearbeiten.
Gardenhead
1
@gardenhead: Danke für deine Antwort! Das ist interessant, aber ich denke nicht, dass dies sehr mit meiner Frage zusammenhängt, oder? Dies zeigt nur, dass # BIPARTITE-MATCHING in #P ist, was keine große Überraschung ist.
A3nm
Die Reduzierung dieser Antwort scheint richtig zu sein, obwohl sie nichts mit der Frage zu tun zu haben scheint. Ich verstehe jedoch weder den Kommentar von @ a3nm noch folge ich der Geschichte im Vorwort der Antwort (die eher drei verschiedene Reduzierungen durcheinander bringt).
András Salamon
Ich habe herausgefunden, wie man # MONO-2SAT auf #BIPARTITE PERFECT MATCHING reduziert, aber der Beweis ist nicht so einfach: P.