2

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.

John L.
  • 38,985
  • 4
  • 33
  • 90
Rob32409
  • 115
  • 6

1 Answers1

4

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?

John L.
  • 38,985
  • 4
  • 33
  • 90
  • They are paths. – Rob32409 Nov 19 '21 at 04:10
  • Right. There is a problem about finding a path that is also a spanning tree. What is that problem? – John L. Nov 19 '21 at 05:15
  • The Hamiltonian path problem? – Rob32409 Nov 19 '21 at 05:39
  • 2
    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? – Rob32409 Nov 19 '21 at 09:30
  • 1
    Cool, that is correct. – John L. Nov 19 '21 at 09:35
  • God answer and following dialogue, but I think the answer will be even better off you incorporate the "dialog findings" – Pål GD Nov 20 '21 at 20:03