Überspannende Spinnen finden

Gibt es einen Polynom-Zeit-Algorithmus, um - falls vorhanden - eine überspannende Spinne eines gegebenen Graphen ? Eine Spinne ist ein Baum mit höchstens einem Knoten mit einem Grad größer als 2: Ich weiß, dass verschiedene Gradbedingungen auf (im Wesentlichen ausreichend große Knotengrade) die Existenz einer überspannenden Spinne garantieren. Aber ich frage mich, ob es einen Algorithmus für beliebiges . Vielen Dank! $G$
Geben Sie hier die Bildbeschreibung ein
$G$ $G$

ds.algorithms reference-request graph-theory graph-algorithms Joseph O'Rourke
quelle

Das Googeln von "Spanning Spiders NP-complete" zeigte als erstes Ergebnis eine Version des Artikels von Gargano, Hammar, Hell, Stacho und Vaccaro 2004 . Satz 1 besagt, dass es NP-vollständig ist. Beantwortet das deine Frage?

Tsuyoshi Ito

Scheint, dass man das Hamiltonsche Pfadproblem leicht darauf reduzieren kann. Wenn , machen Sie zwei Kopien und fügen Sie für einen beliebigen Scheitelpunkt eine Kante , die die beiden Kopien von . Jede überspannende Spinne in dem resultierenden Graphen muss kreuzen und auf einer der beiden Kopien ein Hamilton-Pfad sein.

G

$G$

G_{1}, G_{2}

$G_1,G_2$

v \in G

$v \in G$

e

$e$

v

$v$

H

$H$

e

$e$

Chandra Chekuri

Danke, Tsuyoshi & Chandra! Ja, das beantwortet meine Frage. Ich stieß auf einen Hinweis auf das Gargano-Papier, jedoch nicht auf NP-Vollständigkeit, sondern auf deren ausreichenden Zustand für die Existenz einer überspannenden Spinne.

Joseph O'Rourke

Idealerweise hätten sie ihre Kommentare als Antworten gepostet :), aber Ihre Lösung funktioniert auch

Suresh Venkat

@Suresh: Falls Sie es nicht wissen, habe ich es nicht als Antwort gepostet, weil ich nicht dachte, dass diese Frage hier überhaupt hätte gestellt werden sollen.

Tsuyoshi Ito

Überspannende Spinnen finden

Antworten: