<p>The question has been answered in the comments by Tsuyoshi &amp; Chandra!  I am adding this CW answer so I can accept it to indicate the question is closed.  Thanks, everyone!</p>

CC BY-SA 3.0
2011-10-09T06:54:02.747Z
IIRC you need to wait 2 days after posting a question to accept your own answer.
Kaveh
CC BY-SA 3.0
2011-10-08T14:55:50.620Z
2011-10-08T14:55:50.620Z
Joseph O'Rourke
<p>Is there a polynomial-time algorithm to find&mdash;if one exists&mdash;a spanning spider
of a given graph $G$?  A spider is a tree with at most one node with degree greater than 2:
<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="https://i.sstatic.net/VQla6.jpg" alt="enter image description here"><br />
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!</p>

CC BY-SA 3.0
2011-10-07T17:53:02.527Z
Googling “spanning spiders NP-complete” showed a version of [the article by Gargano, Hammar, Hell, Stacho, and Vaccaro 2004](http://dx.doi.org/10.1016/j.disc.2004.04.005) as the first result.  Proposition 1 states that it is NP-complete.  Does this answer your question?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-07T18:04:33.087Z
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.
Chandra Chekuri
CC BY-SA 3.0
2011-10-07T19:54:59.707Z
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.
Joseph O'Rourke
CC BY-SA 3.0
2011-10-08T19:35:47.013Z
ideally they would have posted their comments as answers :), but your solution works as well
Suresh Venkat
CC BY-SA 3.0
2011-10-08T21:53:04.053Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-08T23:50:44.833Z
@Chandra, please convert your comment into an answer.
Mohammad Al-Turkistany
<ds.algorithms><reference-request><graph-theory><graph-algorithms>
Finding spanning spiders
Joseph O'Rourke
# Finding spanning spiders

(Asked by: username_0 on 2011-10-07)

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](https://i.sstatic.net/VQla6.jpg)  
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!

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Googling “spanning spiders NP-complete” showed a version of [the article by Gargano, Hammar, Hell, Stacho, and Vaccaro 2004](http://dx.doi.org/10.1016/j.disc.2004.04.005) as the first result.  Proposition 1 states that it is NP-complete.  Does this answer your question?  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: ideally they would have posted their comments as answers :), but your solution works as well  
> **username_1**: @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.  
> **username_4**: @Chandra, please convert your comment into an answer.  

---

## 1 answers

### Answer by username_0 on 2011-10-08. Score: 4 | Accepted answer

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!

> **Comments:**
> **username_5**: IIRC you need to wait 2 days after posting a question to accept your own answer.  

---

