10
$\begingroup$

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:
          enter image description here
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!

$\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$ Oct 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$ Oct 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$ Oct 7, 2011 at 19:54
  • 1
    $\begingroup$ ideally they would have posted their comments as answers :), but your solution works as well $\endgroup$ Oct 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$ Oct 8, 2011 at 21:53

1 Answer 1

4
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ IIRC you need to wait 2 days after posting a question to accept your own answer. $\endgroup$
    – Kaveh
    Oct 9, 2011 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.