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$ – Tsuyoshi Ito Oct 7 '11 at 17:53
  • 13
    $\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 Chekuri Oct 7 '11 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'Rourke Oct 7 '11 at 19:54
  • 1
    $\begingroup$ ideally they would have posted their comments as answers :), but your solution works as well $\endgroup$ – Suresh Venkat Oct 8 '11 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 Ito Oct 8 '11 at 21:53
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 '11 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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