Is there a polynomial-time algorithm to find—if one exists—a spanning spider
of a given graph $G$? A spider is a tree with at most one node with degree greater than 2:
I know that various degree conditions on $G$ (essentially, sufficiently large node degrees) guarantee the existence of a spanning spider. But I am wondering if there is an algorithm for arbitrary $G$. Thanks!
$\begingroup$
$\endgroup$
6
-
9$\begingroup$ Googling “spanning spiders NP-complete” showed a version of the article by Gargano, Hammar, Hell, Stacho, and Vaccaro 2004 as the first result. Proposition 1 states that it is NP-complete. Does this answer your question? $\endgroup$– Tsuyoshi ItoOct 7, 2011 at 17:53
-
14$\begingroup$ Seems that one can easily reduce Hamiltonian path problem to this. Given $G$, make two copies $G_1,G_2$ and for some arbitrary vertex $v \in G$ add an edge $e$ that joins the two copies of $v$. Any spanning spider in the resulting graph $H$ has to cross $e$ and be a Hamiltonian path on one of the two copies. $\endgroup$– Chandra ChekuriOct 7, 2011 at 18:04
-
1$\begingroup$ Thanks, Tsuyoshi & Chandra! Yes, that answers my question. I encountered a reference to the Gargano paper but not for NP-completeness, rather for their sufficient condition for the existence of a spanning spider. $\endgroup$– Joseph O'RourkeOct 7, 2011 at 19:54
-
1$\begingroup$ ideally they would have posted their comments as answers :), but your solution works as well $\endgroup$– Suresh VenkatOct 8, 2011 at 19:35
-
$\begingroup$ @Suresh: In case you are not aware, I did not post it as an answer because I did not think that this question should have been asked here in the first place. $\endgroup$– Tsuyoshi ItoOct 8, 2011 at 21:53
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
The question has been answered in the comments by Tsuyoshi & Chandra! I am adding this CW answer so I can accept it to indicate the question is closed. Thanks, everyone!
-
1$\begingroup$ IIRC you need to wait 2 days after posting a question to accept your own answer. $\endgroup$– KavehOct 9, 2011 at 6:54