NP vollständige Graphprobleme über Struktureigenschaften

(Diese Frage ist eine Art "Umfrage".)

Ich arbeite derzeit an einem Problem, bei dem ich versuche, die Ränder eines Turniers in zwei Gruppen zu unterteilen, die beide erforderlich sind, um einige strukturelle Eigenschaften zu erfüllen. Das Problem "fühlt" sich ziemlich schwer an und ich erwarte, dass es vollständig Aus irgendeinem Grund fällt es mir schwer, ähnliche Probleme in der Literatur zu finden. $\mathcal{NP}$

Ein Beispiel für ein Problem, das ich als vergleichbar mit dem betrachte, mit dem ich mich befasse:

Gibt es bei einem gewichteten Turnier einen Rückkopplungsbogen in dessen Kanten die Dreiecksungleichung erfüllen? $G = (V,E,w)$ $G$

Beachten Sie den Unterschied zum herkömmlichen Problem mit Rückkopplungsbogensätzen: Die Größe des Satzes ist mir egal, aber es ist mir wichtig, ob der Satz selbst eine bestimmte strukturelle Eigenschaft aufweist.

Sind Sie auf Entscheidungsprobleme gestoßen, die sich ähnlich anfühlen? Erinnerst du dich, ob sie -vollständig waren oder in ? Irgendeine und alle Hilfe geschätzt. $\mathcal{NP}$ $\mathcal{P}$

cc.complexity-theory reference-request np-hardness G. Bach
quelle

Vielleicht kannst du die strukturellen Eigenschaften deines Problems erklären, es gibt hier viele Experten, die mit NPC-Beweisen vertraut sind, und anstelle einer Referenz könntest du einen NPC-Beweis erhalten :-)

Marzio De Biasi

@MarzioDeBiasi Ich würde es sehr gerne vermeiden, einen Beweis für das Problem zu erhalten, mit dem ich mich befasse. Es ist das erste Mal, dass ich wirklich recherchiere und ich würde gerne sehen, wo ich alleine hinkomme :)

G. Bach

Für mich klingt die Frage zu vage und es ist schwer zu erraten, was wirklich gefragt wird. Wahrscheinlich sollte die Frage präzisiert werden: Was meinen Sie mit "sich ähnlich fühlen" und was meinen Sie mit "einem in G gesetzten Rückkopplungsbogen, dessen Kanten die Dreiecksungleichung erfüllen"? Möchten Sie einen Verweis auf das Problem mit dem Rückkopplungslichtbogensatz oder auf ein anderes Problem?

Yoshio Okamoto

@YoshioOkamoto Mir ist klar, dass die Frage mehrdeutig ist, und ich hoffte, dass das Beispiel einiges klarstellen würde. Mit "Rückkopplungsbogenmenge in G, deren Kanten die Dreiecksungleichung erfüllen" meine ich: Wenn

eine Rückkopplungsbogenmenge ist und

, dann

F

$F$

(a, b)

$(a,b)$

(b, c)

$(b,c)$

(a, c)

$(a,c)$

\in F

$\in F$

w (a, b) + w (b, c) \geq w (a, c)

$w(a,b) + w(b,c) \ge w(a,c)$ muss halten, damit

diese Eigenschaft erfüllt. Bisher nur ich je erlebt Probleme der Art

, aber ich möchte, dass

eine Eigenschaft hat, die nicht mit seiner Kardinalität zusammenhängt.

F

$F$

| F | \leq k

$|F| \le k$

F

$F$

G. Bach

Kann jemand einen Link / Verweis auf "das traditionelle Problem mit dem Feedback-Bogensatz" geben ...?

vzn

Antworten:

Ich denke, es gibt viele ähnliche Probleme. Hier sind zwei in Vertex-Version und eine in Edge-Version:

1) Verfügt ein gegebener Graph über einen unabhängigen Rückkopplungsscheitelpunktsatz? (Die Größe des Sets ist uns egal). Dieses Problem ist NP-vollständig; Der Beweis kann aus dem Beweis von Satz 2.1 in Garey, Johnson & Stockmeyer abgeleitet werden .

2) Hat ein gegebener Graph eine Scheitelpunktabdeckung , die einen Baum induziert ? (Die Größe des Sets ist uns egal). Diese Arbeit liefert einen NP-Vollständigkeitsnachweis für dieses Problem (Satz 2); auch für zweiteilige Graphen.

3) Hat ein gegebener Graph eine dominierende Kante, deren Kanten einen induzierten regulären Teilgraphen bilden $1$ ? (Auch bekannt als dominierendes induziertes Matching oder effizientes Kanten-Dominieren. Die Vertex-Version wird in der zweiten Antwort von Mohammad angegeben. Auch hier ist uns die Größe der Menge egal.) Dieses Problem ist NP-vollständig (bekannt, zuerst hier bewiesen ), auch für planare zweigliedrige Graphen.

Die ersten beiden Probleme sind spezielle Beispiele für die Problemklasse stable- : Sei eine Grapheneigenschaft. Hat ein gegebener Graph eine Scheitelpunktabdeckung, die erfüllt ? Weitere NP-vollständige Fälle sowie polynomiell lösbare Fälle finden Sie in diesem und in diesem Artikel (und den dort angegebenen Quellenangaben). $\pi$ $\pi$ $\pi$

vb le
quelle

Das sind genau die Probleme, nach denen ich suche!

G. Bach

@ G.Bach Da dies genau Ihre Frage beantwortet, empfehle ich Ihnen, die Antwort zu akzeptieren und das Kopfgeld zu gewähren.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany Ich stimme zu; Aus irgendeinem Grund kann ich das Kopfgeld nur in einer Stunde vergeben.

G. Bach

Danke für deinen netten Beitrag. Ich dachte eine Weile lang die gleichen Zeilen.

Mohammad Al-Turkistany

$C$ $C$ $NP$ $NP$

DW Bange, AE Barkauskas und PJ Slater. Effiziente dominierende Mengen in Diagrammen . Anwendungen der diskreten Mathematik, Proc. 3rd SIAM Conf., Clemson / South Carolina 1986, 189-199 (1988)., 1988.

Mohammad Al-Turkistany
quelle

Andere Varianten von Dominating Set sind Connected Dominating Set und Independent Dominating Set .

Radu Curticapean

@RaduCurticapean Aber bei diesen Varianten ist Ihnen die Größe der Lösung wichtig.

Ja, ich habe das übersehen.

Radu Curticapean

$NP$ $NP$

Ein Loch ist ein akkordloser Zyklus mit einer Länge von mehr als drei. Ein Zyklus in einem gerichteten Graphen ist akkordlos, wenn seine Länge größer als 3 ist und keine zwei seiner Scheitelpunkte durch eine Kante des gerichteten Graphen verbunden sind, die nicht zum Zyklus gehört.

$NP$ $P$

$NP$

Die Bedeutung der Erkennung von ungeraden Lochstrukturen in Graphen wird durch den jüngsten Durchbruch des Strong Perfect Graph Theorem unterstrichen . Es zeigt, dass ein Diagramm genau dann perfekt ist, wenn weder es noch sein komplementäres Diagramm ein ungerades Loch aufweisen.

Mohammad Al-Turkistany
quelle

Ein Zyklus ist genau dann ein induzierter Zyklus, wenn es sich um einen akkordlosen Zyklus handelt (auch Loch genannt).

Mohammad Al-Turkistany

Ihre beiden Antworten klingen wie das Problem, nach dem ich suche, danke!

G. Bach