2
$\begingroup$

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?

I think it is and I'm trying to prove it. So far I've tried to reduce Vertex Cover to this problem. My idea is that the internal nodes of a spanning tree of $G$ form a vertex cover of $G$, but I'm stuck at trying to relate the internal nodes to the number of leaves of the spanning tree.

Improve this question
$\endgroup$
4
$\begingroup$

Yes, this problem is indeed $\text{NP}$-hard.

Here is a hint of proof. Draw several trees with 2 leaves. What kind of graphs are they?

Improve this answer
$\endgroup$
6
  • $\begingroup$ They are paths. $\endgroup$
    – Rob32409
    Nov 19 at 4:10
  • $\begingroup$ Right. There is a problem about finding a path that is also a spanning tree. What is that problem? $\endgroup$
    – John L.
    Nov 19 at 5:15
  • $\begingroup$ The Hamiltonian path problem? $\endgroup$
    – Rob32409
    Nov 19 at 5:39
  • 2
    $\begingroup$ I've come up with this. Let $s$ and $t$ be two nodes in $G$. Let $G'$ be a new graph made of $G$ plus 25 new vertices connected to $s$ and $25$ new vertices connected to $t$. Then, then the existence of a Hamiltonian Path in $G$ implies that there is spanning tree in $G'$ with at most 50 leaves. Is this correct? $\endgroup$
    – Rob32409
    Nov 19 at 9:30
  • 1
    $\begingroup$ Cool, that is correct. $\endgroup$
    – John L.
    Nov 19 at 9:35

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.