NP-vollständiger Beweis vom Dasgupta-Problem auf Kite

Ich versuche, dieses Problem anhand von Algorithmen zu verstehen . von S. Dasgupta, CH Papadimitriou und UV Vazirani, Kapitel 8 , S. 281. Problem 8.19

Ein Drachen ist ein Graph auf einer geraden Anzahl von Eckpunkten, beispielsweise , in dem der Eckpunkte eine Clique bilden und die verbleibenden Eckpunkte in einem „Schwanz“ verbunden sind, der aus einem Pfad besteht, der mit einem der Eckpunkte der Clique verbunden ist . Wenn ein Graph und ein Ziel , fragt das KITE-Problem nach einem Untergraphen, der ein Kite ist und Knoten enthält . Beweisen Sie, dass KITE NP-vollständig ist. $2n$ $n$ $n$ $G$ $g$ $2g$

Gibt es Hinweise, um mit diesem Problem zu beginnen? Ich bin völlig verloren damit.

complexity-theory np-complete reductions John
quelle

Antworten:

Sie können CLIQUE ( hat eine Clique der Größe ) auf KITE reduzieren: Wenn und , bauen Sie einfach in Polynomzeit einen neuen Graphen auf diese Weise auf: Sie für jeden Knoten einen Schwanz von neue Knoten. $G$ $k$ $G=(V,E)$ $k$ $G'$ $v_i$ $k$

Wenn einen Drachen der Größe dann hat der eine Clique der Größe (der Drachen ohne Schwanz). Hinzugefügte Knoten können keine neuen Cliquen auf G 'einführen, daher enthält genau die gleichen Cliquen von . $G'$ $2k$ $G$ $k$ $G$ $G'$

Vor
quelle

Warum die Knoten des Grades 1 löschen? Wenn eine Klasse hat, dann hat einen Drachen, und wenn einen Drachen hat, dann hat eine Klasse (mit dem zufälligen Fall, dass wenn einen Drachen hat, ) . Wenn wir nicht nach einem induzierten Untergraphen fragen, ist es möglich, dass nach dem Löschen der Eckpunkte des Grades 1 ohnehin noch einen Drachen hat.

G

$G$

k

$k$

G^{'}

$G'$

2 k

$2k$

G^{'}

$G'$

2 k

$2k$

G

$G$

k

$k$

G

$G$

G^{'}

$G'$

G

$G$

2 k

$2k$

Luke Mathieson

@ LukeMathieson: Sie haben Recht, es ist kein induzierter Subgraph. Ich habe die Antwort geändert

Vor

Ist es notwendig, v ' Schwänze der Länge k zu G' hinzuzufügen ? Wäre nicht 1 Schwanz der Länge k ausreichend? Ich davon aus, dass jeden Scheitelpunkt im Diagramm bedeutet.

v_{i}

$v_i$

v_{i}

$v_i$

DanGoodrick