Zeigen, dass das minimale Löschen von Scheitelpunkten in einem zweigeteilten Diagramm NP-vollständig ist

Betrachten Sie das folgende Problem, dessen Eingabeinstanz ein einfacher Graph und eine natürliche ganze Zahl . $G$ $k$

Gibt es eine Menge so dass zweigeteilt ist und ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Ich möchte zeigen, dass dieses Problem ist -komplette entweder durch 3-SAT, wodurch -CLIQUE, -DOMINATING SET oder -eckiges COVER zu. $\rm{NP}$ $k$ $k$ $k$

Ich glaube, ich kann das 3-COLORING-Problem darauf reduzieren, sodass ich nur sehen muss, wie ich eines der genannten Probleme darauf reduzieren kann. Aber da das ziemlich chaotisch wäre, frage ich mich, ob jemand eine elegante Reduktion auf die oben genannten Probleme sieht.

Gibt es auch einen Namen für dieses Entscheidungsproblem?

complexity-theory np-complete reductions Jernej
quelle

Odd Cycle Transversal .

Pål GD

Dies scheint dem Feedback-Vertex-Set ähnlich zu sein . Das heißt, Sie möchten eine minimale Teilmenge der zu entfernenden Scheitelpunkte finden, sodass der resultierende Graph azyklisch ist. Ein azyklischer Graph ist per Definition ein Baum (oder Wald), der zweiteilig ist.

Nicholas Mancuso

@NicholasMancuso Es ist nicht so ähnlich. Es ist wirklich, wie ich oben sage, das Odd Cycle Transversal-Problem. Oder wie Vor betont, wurde Yannakakis in den 70er und 80er Jahren die Löschung des zweigliedrigen Knotens (oder Scheitelpunkts) genannt.

Pål GD

@ PålGD, ich stimme zu. Ich hatte das Gefühl, dass die einfachste Reduzierung von FVS ausgehen würde. Dies wird jedoch durch die Definition als Odd Cycle Transversal unnötig.

Nicholas Mancuso

@Jernej: Sie sagen "... Ich möchte zeigen, dass dieses Problem in NP liegt, indem Sie es entweder auf 3-SAT, die k-CLIQUE, ... reduzieren ." Meinen Sie "Ich möchte zeigen, dass dieses Problem mit einer Reduktion von 3-SAT, k-CLIQUE, ... NP-schwer ist "? (Das Problem liegt eindeutig in NP, da das Testen, ob ein Graph zweiteilig ist, in linearer Zeit durchgeführt werden kann.)

Vor dem

Antworten:

Ihr Problem ist ein Sonderfall einer breiteren Klasse von Problemen, die als Probleme beim Löschen von Knoten bezeichnet werden :

JM Lewis und M. Yannakakis, "Das Problem der Knotenlöschung für erbliche Eigenschaften ist NP-vollständig"

... In diesem Artikel wird die Klasse der Diagrammprobleme behandelt, die wie folgt definiert sind: Ermitteln Sie
für eine feste Diagrammeigenschaft die Mindestanzahl von Knoten (oder Scheitelpunkten), die aus einem bestimmten Diagramm gelöscht werden müssen, damit das Ergebnis erfüllt . Wir nennen dies das Knotenlöschproblem für . Unsere Ergebnisse zeigen, dass, wenn eine nichttriviale Eigenschaft ist, die auf einem induzierten Subgraphen erblich ist , das Knotenlöschproblem für NP-schwer ist. Wenn wir außerdem die Bedingung hinzufügen, dass das Testen auf $\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ kann in Polynomzeit durchgeführt werden, dann implizieren unsere Ergebnisse, dass das Knotenlöschproblem für NP-vollständig ist. ... $\Pi$

Ihr Problem ist das Problem der Knotenlöschung für die Zweiteiligkeit , aber (wie von Pal festgestellt) ist es heute als das Odd Cycle Traversal (OCT) -Problem bekannt.

BEARBEITEN

Für eine direkte Reduzierung habe ich an diese von 3SAT gedacht.

Erstellen Sie bei einer Instanz von 3SAT mit Variablen und Klauseln das folgende Diagramm: für jede Variable zwei Knoten und eine Kante dazwischen hinzu. Um eine Wahrheitszuweisung zu simulieren, fügen Sie Knoten für jede Variable und verbinden Sie beide mit und ; Auf diese Weise muss mindestens einer zwischen und gelöscht werden, damit ein zweigeteilter Graph höchstens Knoten löscht . Sie schließlich für jede Klausel 4 Knoten hinzu und erstellen Sie einen ungeraden Zyklus, der die Variablen in . $n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ $C_j$ $C_j$

Der resultierende Graph kann genau dann an den meisten Knoten zweigeteilt gelöscht werden, wenn die ursprüngliche 3SAT-Formel erfüllt werden kann. $G$ $n$

Geben Sie hier die Bildbeschreibung ein

Vor
quelle

Dies ist nicht wirklich die Antwort, nach der die Frage fragt. OP möchte das angegebene Problem explizit reduzieren. Darüber hinaus ist das Problem heute als Odd Cycle Transversal bekannt.

Pål GD

@ PålGD: Du hast recht.

Vor dem

Ja, aber ich kann nicht sofort eine Reduzierung von OPs Liste der Probleme sehen ... Ich kenne nur die von Ihnen erwähnte von Yannakakis.

Pål GD

@ PålGD: Ich werde über eine andere Reduzierung nachdenken, aber um ehrlich zu sein, bin ich mir nicht sicher, was genau das OP will (siehe meinen Kommentar oben).

Vor dem

@Vor Was ich möchte, ist eine einfache Reduktion auf eines von einem der genannten Probleme. Dieser Artikel ist mir bekannt, aber ich suche eher die direkteste Reduktion.

Jernej