Finden einer Übereinstimmung, deren Kontraktion die Anzahl der Bögen in einem Diagramm minimiert

Wenn ein gemischter Graph mit den Kanten und den Bögen , finden Sie in eine Übereinstimmung , die die Anzahl der Bögen in minimiert , wobei aus indem übereinstimmende Eckpunkte zusammengezogen und entfernt werden parallele Bögen.E A E G / M G / M $G=(V,E,A)$$E$$A$$E$$G/M$$G/M$$G$

Ist (die Entscheidungsversion von) dieses Problem NP-vollständig? Wurde es in der Literatur studiert?

Ich weiß nicht, ob Sie beabsichtigen, ungerichtete Kanten in E und Bögen in A parallel zu lassen oder nicht, aber es spielt am Ende keine Rolle. In dieser Antwort wird davon ausgegangen, dass Sie nicht zulassen, dass Kanten und Bögen parallel sind.

Betrachten wir einen speziellen Fall , in dem für jeden Bogen in A , A auch die Bogenrichtung in der entgegengesetzten enthält. In diesem Fall können wir die Ausrichtung von Bögen ignorieren und sie als ungerichtet betrachten. Wir nennen Kanten in E schwarze Kanten und Kanten in A roten Kanten .

Selbst unter diesen beiden Einschränkungen ist das Problem durch eine Reduzierung von Max-2SAT NP-vollständig. Sei φ eine 2CNF-Formel in n Variablen n$x_1,\dots,x_n$ mit m Klauseln. Konstruieren Sie einen Graphen G mit 3 n Eckpunkten wie folgt. G hat 2$v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$ schwarze Kanten: und ( v i , ˉ x i ) für i = 1,…, n . G hat rote Ränder. Verbinden Sie zuerst und für i ≠ j durch eine rote Kante. Als nächstes betrachten für jede unterschiedliche Variable und vier Literalpaare . Literale verbinden$(v_i,x_i)$$(v_i,\bar{x}_i)$vivjxixj(l,l')=(xi,xj),(xi, ˉ x j),( ˉ x i,xj),( ˉ x i, ˉ x j)ll'( ˉ l$5\binom{n}{2}-m$$v_i$$v_j$$x_i$$x_j$$(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$$l$und durch eine rote Kante, wenn und nur wenn Klausel nicht in φ erscheint .$l'$$(\bar{l}\vee\bar{l}')$

Es ist klar, dass wir nur maximale Übereinstimmungen in schwarzen Rändern berücksichtigen müssen, um die Anzahl der roten Ränder nach der Kontraktion zu minimieren. Es ist auch klar, dass jedes maximal übereinstimmende M in schwarzen Kanten aus n Kanten besteht, die mit für i = 1,…, n verbinden . Identifizieren Sie diese maximal übereinstimmende M mit der Wahrheitszuweisung . Es ist leicht zu überprüfen, ob der Graph nach dem Zusammenziehen von M und dem Entfernen paralleler Kanten genau rote Kanten hat, wobei kl i ∈ { x i , ˉ x i } { l 1 , … , l n } 4 ($v_i$$l_i\in\{x_i,\bar{x}_i\}$$\{l_1,\dots,l_n\}$$4\binom{n}{2}-k$ist die Anzahl der Klauseln, die durch diese Wahrheitszuweisung erfüllt werden. Das Minimieren der Anzahl roter Kanten nach dem Zusammenziehen einer Übereinstimmung mit schwarzen Kanten entspricht daher dem Maximieren der Anzahl erfüllter Klauseln.