NP-harte Probleme bei cographs

12

Diese Frage ähnelt NP-harten Problemen an Bäumen :

Es gibt eine große Anzahl von NP-vollständigen Problemen, die auf cographs nachvollziehbar sind . Gibt es bekannte Probleme, die NP-vollständig bleiben, wenn sie auf cographs beschränkt sind?

Genauer gesagt interessieren mich Beispiele, bei denen die Eingabe ausschließlich aus einem ungerichteten, ungewichteten cograph besteht .

Zwei Bemerkungen:

Für gewichtete cographs ein solches Problem wird erwähnt hier - TSP mit zwei Reisenden
Cographs sind die "Basisklasse" von clique-width, wie Bäume die Basisklasse für tree-width.

AKTUALISIEREN

Einige weitere Gedanken (da bin ich mir nicht ganz sicher): Wenn die Eingabe wirklich nur ein Cograph ist, muss die Frage von der Art "Hat der Cograph die Eigenschaft X?" Sein. Es wäre ausreichend, wenn ein solches Problem für Bäume bestehen würde, da dann die Frage lauten könnte: "Hat der Cotree des Cograph die Eigenschaft X?".

cc.complexity-theory np-hardness graph-algorithms Martin Lackner
quelle

Um zu verhindern, dass es sich um eine (nicht so) doppelte Frage handelt, müssen diese NP-vollständigen Probleme möglicherweise auch polynomiell zeitlösbar auf Bäumen sein.

Hsien-Chih Chang 張顯之

Wäre natürlich nett. Ich würde jedoch bestritten werden, auch wenn dies nicht der Fall wäre. Zumal alle Beispiele im Original-Thread meine Frage (nach meinem Verständnis) nicht beantworten.

Martin Lackner

11

Vielleicht ist mein offenes Lieblingsproblem von Interesse: das Rand-Clique-Cover-Problem bei Cographs. In dem Rand-Clique-Cover-Problem möchten Sie die Ränder des Cographs mit einer minimalen Anzahl von Cliquen abdecken. Es ist nicht bekannt, ob dieses Problem NP-vollständig ist.

Um zu veranschaulichen, dass das Problem wahrscheinlich schwierig ist, sei der vollständige mehrteilige Graph mit jeweils Partitensätzen der Größe . Dies ist eine Aufzeichnung. Es existiert paarweise orthogonale lateinische Quadrate der Ordnung , wenn und nur wenn die Kante Clique-Abdeckung von ist . Dies wurde von Park, Kim und Sano gezeigt . Dies ist eine Formel für das "Cocktailparty-Diagramm", dh für den Fall, dass . $K_n^m$ $m$ $n$ $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Ton Kloks
quelle

10

Einige Probleme bleiben NP-vollständig, wenn sie sich auf cographs beschränken. Die Listenfärbung, die achromatische Zahl und der induzierte Subgraph-Isomorphismus bleiben NP-vollständig.

[1] Hans L. Bodlaender. Die achromatische Zahl ist für cographs und Intervallgraphen NP-vollständig. Inf. Prozess. Lett., 31 (3): 135–138, 1989

[2] Klaus Jansen und Petra Scheffler. Verallgemeinerte Färbung für baumähnliche Diagramme. Diskrete Appl. Math., 75 (2): 135–155, 1997

[3] Peter Damaschke. Der induzierte Subgraph-Isomorphismus für cographs ist NP-vollständig. Lecture Notes in Computer Science, 1991, Band 484/1991, 72-78,

Mohammad Al-Turkistany
quelle

1

Vielen Dank für Ihre Antwort. Dies sind wirklich interessante Probleme, aber ich denke, sie erfüllen nicht die Anforderung, dass die Eingabe nur ein Graph ist: Die Eingabe in [1] ist ein Graph und eine ganze Zahl, [2] ein Graph und eine Menge von Farben für jeden Scheitelpunkt, [ 3] zwei Graphen.

Martin Lackner

3

Hier sind triviale Variationen von zwei der gleichen Probleme, die NP-vollständig bleiben, aber nur einen cograph als Eingabe haben: Besteht der gegebene cograph aus zwei verbundenen Komponenten, von denen eine ein induzierter Subgraph der anderen ist? Hat die angegebene Grafik eine vollständige Färbung, die jedem der isolierten Scheitelpunkte eine eigene Farbe verleiht?

David Eppstein

10

$G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

vb le
quelle

2

Dies kann wiederum als Problem auf einer einzelnen Aufzeichnung interpretiert werden (die zufällig zwei verbundene Komponenten aufweist).

David Eppstein

1

Aha. Natürlich kann man nach NP-vollständigen Problemen fragen, bei denen die Eingabe nur aus einem zusammenhängenden , ungerichteten, ungewichteten cograph besteht. Ich denke, die Frage ist sehr interessant.

VB Le

1

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

David Eppstein

Ah, das ist gut!

VB Le

NP-harte Probleme bei cographs

Antworten: