Polynomprobleme in Graphklassen, die durch verbotene induzierte zyklische Subgraphen definiert sind

11

Crossposted von MO .

Sei eine Graphklasse, die durch eine endliche Anzahl verbotener induzierter Untergraphen definiert ist, die alle zyklisch sind (mindestens einen Zyklus enthalten). $C$

Gibt es NP-harte Graphprobleme, die in der Polynomzeit für außer Clique und Clique Cover gelöst werden können ? $C$

Wenn ich mich richtig erinnere, ist dies für eine unabhängige Menge unmöglich (es sei denn, ). $P=NP$

Die Suche in graphclasses.org hat keine gefunden.

Eine Klasse, für die Clique und Clique Polynom sind, ist C5, C6, X164, X165, Sunlet4, dreieckfrei

Bearbeiten

Negativ für IS und Dominanz ist in diesem Artikel . Seite 2, die Graphen . $S_{i,j,k}$

cc.complexity-theory graph-theory graph-algorithms co.combinatorics joro
quelle

3

In Stefan Kratsch, Pascal Schweitzer, Graphisomorphismus für durch zwei verbotene induzierte Untergraphen charakterisiert sind : GI ist die (trivial) lösbare für Graphen, aber auch (weniger trivial) für Graphen.

(K_{s}, I_{t}) -free

$(K_s, I_t)\text{-free}$

(K_{s}, K_{1, t}) -free

$(K_s, K_{1,t})\text{-free}$

Marzio De Biasi

2

Vielleicht ist es am besten, bei der Frage auf MO auch das Cross-Posting zu notieren. Wenn jemand dort interessiert ist, möchte er vielleicht die Antworten / Kommentare hier sehen.

RB

1

@MarzioDeBiasi, warum nicht Ihren Kommentar zur Antwort drehen?

Saeed

14

Ich denke, es gibt eine Reihe schwieriger Probleme, die für dreieckfreie Diagramme leicht werden. Insbesondere befassen sich diese direkt mit Dreiecken wie Partition in Dreiecke (Hat G eine Partition in Dreiecke?). Andere weniger triviale Beispiele sind:

Stabiles Cutset-Problem (Hat G eine unabhängige Menge S, so dass GS nicht verbunden ist?). Siehe: Auf stabilen Sutsets in Diagrammen, Discrete Applied Math. 105 (2000) 39-50.
Schnittdiagrammbasis (Ist G das Schnittdiagramm von Teilmengen einer k-Element-Grundmenge?). Siehe: Problem [GT59] in: Garey & Johnson, Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit.

Mon Tag
quelle

11

Hier sind einige zusätzliche Beispiele für die Antwort von Mon Tag:

Das Disconnected Cutset-Problem (Gibt eine Menge von Eckpunkten so dass und der durch induzierte Teilgraph von getrennt sind) ist NP-vollständig (siehe hier ). Es ist leicht zu erkennen, dass dieses Problem für dreieckfreie Graphen polynomiell lösbar ist (daher auch das von Mon Tag erwähnte Problem des stabilen Cutset). $G$ $S$ $G-S$ $G$ $S$
Das Erkennen von Dreiecksliniendiagrammen ist NP-vollständig (siehe hier ). Es ist auch leicht zu erkennen, dass dieses Problem für dreieckfreie Eingabegraphen polynomiell wird.
Die Berechnung der maximal verbundenen Übereinstimmung ist schwierig (siehe hier . Eine Übereinstimmung ist verbunden, wenn für ein Paar der Übereinstimmungskanten eine andere Kante des Diagramms auf beide einfällt). Es kann bewiesen werden, dass dieses Problem für -freie Graphen polynomiell lösbar ist . $(C_3, C_4, C_5)$

vb le
quelle

Vielen Dank. Einige Probleme bleiben also schwierig, andere nicht.

Joro

10

Aus dem obigen Kommentar: In Stefan Kratsch, Pascal Schweitzer, Graphisomorphismus für charakterisiert durch zwei verbotene induzierte Untergraphen : GI ist die (trivial) lösbare für Graphen, aber auch (weniger) trivial) für Graphen. $(K_s,I_t)\text{-free}$ $(K_s,K_{1,t})\text{-free}$

BEARBEITEN : Wie im Kommentar erwähnt, enthält keinen Zyklus (ich habe die Einleitung des Papiers zu schnell gelesen). $K_{1,t}$

Nachdem Sie ein wenig darüber nachgedacht haben, scheint es einfach zu sein, Folgendes zu beweisen (Original?):

NEGATIVES ERGEBNIS: Für jede endliche Menge in der jedes einen Zyklus enthält, beschränkt sich das Problem des Graphisomorphismus (GI) auf die Klasse von -Diagramme sind GI-vollständig. $\{H_1,...H_k\}$ $H_i$ $\mathcal{C}$ $(H_1,...,H_k)\text{-free}$

Beweis: Es wurde eine Klasse von Graphen in denen jedes einen Zyklus enthält, und bei sei die Länge des längsten Zyklus der s. Ersetzen Sie jede Kante von durch einen Pfad der Länge fügen Sie neue Knoten hinzu (siehe Abbildung unten). . Durch die Konstruktion der neuen Graphen sind zwar die möglichen kürzesten Zyklen sind die durch ein Dreieck gebildet , die Länge haben müssen $(H_1,...,H_k)\text{-free}$ $H_i$ $G_1,G_2$ $r$ $H_i$ $(u,v)$ $G_1,G_2$ $l = \lceil r/3 \rceil$ $l$ $(u,p_1,p_2,...,p_l,v)$ $G'_1, G'_2$ $(H_1,...,H_k)\text{-free}$ $3\lceil r/3 \rceil + 3 > r$ ;; und es ist leicht zu beweisen, dass sie genau dann isomorph sind, wenn die ursprünglichen isomorph sind. $G_1,G_2$

Geben Sie hier die Bildbeschreibung ein
Abbildung : links ein Graph und rechts der äquivalente Graph (angenommen, der längste Zyklus des hat die Länge , also Jede Kante von wird durch einen Pfad der Länge . $G_1$ $(H_1,...,H_k)\text{-free}$ $G'_1$ $H_i$ $r=15$ $G_1$ $l = 5$

Wir können das negative Ergebnis auch auf das Hamilton-Zyklus-NPC-Problem ausweiten, tatsächlich ist es eine unmittelbare Folge des Folgenden (Original?):

Satz : Für jedes bleibt das Hamilton-Zyklusproblem NP-vollständig, selbst wenn der Graph keine Zyklen der Länge . $k \geq 3$ $G$ $\leq k$

Beweis Wir wissen, dass das Hamilton-Zyklus-Problem NPC ist, selbst auf einem planar gerichteten Graphen wobei jeder Knoten erfüllt: (Papdimitriou und Vazirani, Über zwei geometrische Probleme im Zusammenhang mit dem Problem des Handlungsreisenden) ). Wir können den Graphen in einen ungerichteten Graphen transformieren indem wir einfach einen Knoten an der eingehenden Kante von Knoten mit und an der ausgehenden Kante von Knoten mit . Dann können wir die Knoten von durch das Gadget in der folgenden Abbildung ersetzen . Es ist leicht zu erkennen, dass es nur zwei gültige Durchquerungen gibt ( $G$ $v$ $outdeg(v) + indeg(v) \leq 3$ $G$ $G'$ $v$ $indeg(v )=1$ $v$ $indeg(v)=2$ $G'$ Zickzack ), die jeden Knoten des Gadgets genau einmal besuchen (rote und grüne Pfade in der Abbildung): Die Gadgets können nicht von oben nach unten durchlaufen werden, da sonst der horizontale (eingehende oder ausgehende) Pfad ausgeschnitten würde. Darüber hinaus können wir genügend Knoten auf den vertikalen / horizontalen Segmenten der Gadgets platzieren und die Anzahl ihrer Zickzacklinien erweitern, um sicherzustellen, dass im Gadget oder in einem Dreieck von 3 miteinander verbundenen Gadgets kein Zyklus der Länge möglich ist. Dies stellt sicher, dass, wenn der resultierende Graph einen Hamilton-Zyklus hat, der ursprüngliche Graph auch einen Hamilton-Zyklus hat (die Umkehrung erfolgt unmittelbar durch die Konstruktion des Gadgets). $\geq k$ $G''$ $G$

Geben Sie hier die Bildbeschreibung ein

Folgerung: Hamilton-Zyklus- und Pfadprobleme bleiben NP-vollständig, auch wenn sie auf -Diagramme beschränkt sind, in denen jedes einen Zyklus enthält. $(H_1,...,H_k)\text{-free}$ $H_i$

Marzio De Biasi
quelle

Vielen Dank. ist ein Baum, also nicht zyklisch oder fehlt mir etwas?

K_{1, t}

$K_{1,t}$

Joro

Du hast recht! Ich habe ein negatives Ergebnis erzielt ... sehen Sie, ob es funktionieren kann oder ob es völlig falsch ist: -S: -S

Marzio De Biasi

Vielen Dank. Sie haben also ein angeblich negatives Ergebnis für den GI- UND Hamilton-Zyklus erhalten?

Joro

Hoffe, das ist richtig, dies wird eine Menge lösen, die graphclasses.org Probleme unbekannt ist.

Joro

1

Nur ein Nitpick, jeder Zyklus sollte etw wie wobei ein Grad des Scheitelpunkts , andernfalls kann Ihr iff-Teil, wenn er nicht korrekt ist, ist isomorph, aber nicht .

(m + 1) d_{i}

$(m+1)d_i$

d_{i}

$d_i$

i

$i$

G_{1}, G_{2}

$G_1,G_2$

G_{1}^{'}, G_{2}^{'}

$G'_1,G'_2$

Saeed

1

MAX-CUT bleibt NP-vollständig.

Lemma 3.2 Simple Max-Cut ist in den folgenden zwei Klassen von Graphen NP-vollständig:

Graphen, die höchstens für jedes . $k$ $k \ge 3$

Sie unterteilen eine Kante zweimal.

Aus "MAX-CUT und Containment-Beziehungen in Grafiken, Marcin Kaminski"

joro
quelle

1

Aber Sie haben nach Problemen gefragt, die in der Polynomzeit gelöst wurden, oder?

Peng O

@PengO in der Tat, aber dies ist ein negatives Ergebnis, so dass es unmöglich ist, polynomisch zu sein. Eine andere Antwort zeigt ebenfalls negative Ergebnisse.

Joro

Polynomprobleme in Graphklassen, die durch verbotene induzierte zyklische Subgraphen definiert sind

Antworten: