# Finding spanning spiders

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!

• 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? Oct 7 '11 at 17:53
• 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. Oct 7 '11 at 18:04
• 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. Oct 7 '11 at 19:54
• ideally they would have posted their comments as answers :), but your solution works as well Oct 8 '11 at 19:35
• @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. Oct 8 '11 at 21:53

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!

• IIRC you need to wait 2 days after posting a question to accept your own answer. Oct 9 '11 at 6:54