Znalezienie rozpinających się pająków

Czy istnieje algorytm wielomianowy do znalezienia - jeśli taki istnieje - pająka rozpinającego danego wykresu ? Pająk to drzewo z co najmniej jednym węzłem o stopniu większym niż 2: Wiem, że różne warunki stopnia na (zasadniczo wystarczająco duże stopnie węzła) gwarantują istnienie pająka rozpinającego. Ale zastanawiam się, czy istnieje algorytm dla arbitralnej . Dzięki! $G$
wprowadź opis zdjęcia tutaj
$G$ $G$

ds.algorithms reference-request graph-theory graph-algorithms Joseph O'Rourke
źródło

Googling „rozpinające pająki NP-zupełne” pokazał pierwszą wersję artykułu Gargano, Hammar, Hell, Stacho i Vaccaro 2004 . Twierdzenie 1 stwierdza, że jest kompletne NP. Czy to odpowiada na twoje pytanie?

Tsuyoshi Ito,

Wydaje się, że można łatwo zredukować do tego problem ścieżki hamiltonowskiej. Biorąc pod uwagę , wykonaj dwie kopie i dla niektórych dowolnych wierzchołków dodaj krawędź która łączy dwie kopie . Każdy pająk łączący na wynikowym wykresie musi przekroczyć i być ścieżką hamiltonowską na jednej z dwóch kopii.

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,

Dzięki, Tsuyoshi i Chandra! Tak, to odpowiada na moje pytanie. Spotkałem się z odniesieniem do papieru Gargano, ale nie do kompletności NP, raczej ze względu na ich wystarczający warunek istnienia pająka rozpinającego.

Joseph O'Rourke,

idealnie opublikowaliby swoje komentarze jako odpowiedzi :), ale twoje rozwiązanie również działa

Suresh Venkat,

@Suresh: W przypadku, gdy nie jesteś tego świadomy, nie opublikowałem go jako odpowiedzi, ponieważ nie sądziłem, że to pytanie powinno być zadane tutaj w pierwszej kolejności.

Tsuyoshi Ito,

Znalezienie rozpinających się pająków

Odpowiedzi: