H-freies Schnittproblem

Angenommen, Sie erhalten einen zusammenhängenden, einfachen, ungerichteten Graphen H.

Das H-freie Schnittproblem ist wie folgt definiert:

Bei einem einfachen, ungerichteten Graphen G gibt es einen Schnitt (Aufteilung der Eckpunkte in zwei nicht leere Mengen, L, R), so dass die durch die Schnittsätze (L und R) induzierten Graphen keinen zu H isomorphen Teilgraphen enthalten .

Wenn beispielsweise H der Graph mit zwei durch eine einzige Kante verbundenen Eckpunkten ist, ist das Problem dasselbe wie das Bestimmen, ob ein Graph zweigeteilt ist und sich in P befindet.

Wenn H ein Dreieck ist, entspricht dies der Eckpunktversion des Problems des monochromatischen Dreiecks .

Ich glaube, ich konnte zeigen, dass, wenn H mit mindestens drei Eckpunkten 2-verknüpft ist, das H-freie Schnittproblem NP-vollständig ist.

Ich konnte keine Hinweise auf dieses Problem finden (und daher auch keine Ergebnisse).

Können wir die Bedingung der 2-Verbundenheit fallen lassen und trotzdem die NP-Vollständigkeit nachweisen?

Kennt jemand bekannte Ergebnisse, die das oben genannte oder ein stärkeres Ergebnis implizieren würden (oder die Sie für relevant halten)?

Sie könnten eher nach dem Begriff "Bipartition" oder "Vertex Partition" oder "Coloring" als nach "Cut" suchen. Verschiedene Verallgemeinerungen der chromatischen Zahl entlang der von Ihnen angedeuteten Linien wurden seit Mitte der 80er Jahre (oder möglicherweise früher) in Betracht gezogen. Es gibt einige frühe, schwer zu findende Referenzen in kanadischen Combinatorics-Konferenzen, aber Sie sollten Cowen, Goddard und Jesurum (JGT oder SODA 1997) und verwandte Referenzen / Zitate prüfen.

Bearbeitet am 15/02/2011

Wie von Aravind und Moron (in den Kommentaren unten) ausgeführt, zeigen die folgenden Referenzen, dass das Problem des freien Schnitts mit Ausnahme der unbedeutenden Fälle NP-hart ist.$H$

D. Achlioptas. Die Komplexität der freien Einfärbbarkeit. Diskrete Mathematik. 165/166 (1997) 21-30. [pdf] .$G$

A. Farrugia. Die Vertex-Aufteilung in fixe additive induzierte erbliche Eigenschaften ist NP-hart. Elektron. J. Combin. 11 (2004) # R46 (9 Seiten).

Mir ist klar, dass dies Ihre Frage (zu Referenzen) möglicherweise nicht direkt beantwortet, aber ich möchte einen möglichen Ansatz für die Anzeige der NP-Härte ohne die 2-verbundene Bedingung skizzieren. Es fehlen zwei Dinge: Eine ist sozusagen ein Beweis für die NP-Härte des „Quellproblems“, und die andere ist, dass ich mich auf eine „farbige“ Version von H-Cut reduziere, die oder kann kann nicht nützlich sein. Was den ersten Engpass angeht, so glaube ich, dass ich einen Beweis dafür habe, dass ich bei der Formalisierung faul bin, und hoffe, dass ich mich bald darum kümmern kann. Ich habe darüber nachgedacht, die farbige Version auf die zu reduzieren, die Sie präsentieren, aber bisher mit wenig Glück. Ich bin auch sehr gespannt auf Ihren Beweis für den Fall, dass H 2-verbunden ist. Können Sie möglicherweise einige Details angeben?

Die farbige Version lautet also wie folgt: Jeder Scheitelpunkt in der Grafik ist mit einer Liste von Farben aus einer Palette P (einer festen, endlichen Menge) ausgestattet. Wir müssen einen Schnitt finden, damit keine Partition eine monochromatische Kopie von H induziert, dh es gibt keine Teilmenge von | H | Scheitelpunkte, die eine Kopie von H induzieren, und die entsprechende Liste von Farben haben einen nicht leeren Schnittpunkt.

Hier ist eine Reduktion von einer eingeschränkten Variante von d-SAT, wobei d | H | ist. (Beachten Sie, dass dies offensichtlich nicht funktionieren würde, wenn d = 2).

Die eingeschränkte Variante von d-SAT ist die folgende:

1. Jede Klausel hat entweder nur positive oder nur negative Literale, lassen Sie mich solche Klauseln als P-Klauseln bzw. N-Klauseln bezeichnen,

2. Jede P-Klausel kann mit einer N-Klausel gepaart werden, sodass die beiden Klauseln denselben Satz von Variablen betreffen.

(Ich habe eine Vorstellung davon, warum diese scheinbar eingeschränkte Version schwierig sein könnte - eine sehr eng damit verbundene Einschränkung ist schwierig, und ich kann mir eine Reduzierung von dort vorstellen, obwohl ich mich leicht irren könnte!)

Angesichts dieses Problems bietet sich die Reduzierung vielleicht an. Der Graph hat einen Eckpunkt für jede Variable der Formel. Erstellen Sie für jede Klausel C_i eine Kopie von H für die Gruppe der Variablen, die an der Klausel teilnehmen, und fügen Sie die Farbe i zu dieser Gruppe von Scheitelpunkten hinzu. Damit ist die Konstruktion abgeschlossen.

Jede Zuordnung entspricht natürlich einem Schnitt:

L = Menge aller Variablen, die auf 0 gesetzt wurden, R = Menge aller Variablen, die auf 1 gesetzt wurden.

Die Behauptung ist, dass eine zufriedenstellende Zuordnung einem monochrom-H-freien Schnitt entspricht.

Mit anderen Worten wäre (L, R), wenn es durch eine zufriedenstellende Zuordnung gegeben ist, so, dass weder L noch R eine monochromatische Kopie von H induzieren. Wenn L eine solche Kopie hat, dann beachte, dass die entsprechende P-Klausel gehabt haben muss Alle Variablen sind auf 0 gesetzt, was der Tatsache widerspricht, dass die Zuweisung zufriedenstellend war. Umgekehrt, wenn R eine solche Kopie hat, müssen für die entsprechende N-Klausel alle Variablen auf 1 gesetzt sein, was wiederum zu Widersprüchen führt.

Betrachten Sie umgekehrt einen Schnitt und setzen Sie die Variablen auf der einen Seite auf 1 und auf der anderen auf 0 (beachten Sie, dass es egal ist, wie Sie dies tun - angesichts der Art der Formel, mit der wir arbeiten, einer Zuweisung und der Umkehrung Version sind nach Maßgabe der Erfüllbarkeit gleichwertig). Wenn eine Klausel durch diese Zuweisung nicht erfüllt wird, können wir sie auf eine monochrome Kopie von H auf einer der Seiten zurückführen, was der monchromatischen H-Freiheit des Schnitts widerspricht.

Der Grund, warum man sich der Färbung hingeben muss, ist, dass Kopien von H stören können, um in einem direkten Reduktionsversuch falsche Kopien von H zu erzeugen, die nicht den Sätzen entsprechen. In der Tat scheitert es - schlimm - auch wenn H so einfach wie ein Pfad ist.

Ich hatte kein Glück, die Farben loszuwerden, und ich bin mir nicht sicher, ob ich das Problem einfacher gemacht habe. Ich hoffe jedoch, dass es - wenn es richtig ist - ein Anfang sein könnte.