2
$\begingroup$

I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

  2. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

$\endgroup$
  • 3
    $\begingroup$ Hint for part 1: What does it mean when G has a spanning tree where every node has at most 2 neighbors? $\endgroup$ – user53923 Dec 4 '17 at 10:35
  • 1
    $\begingroup$ @user53923 maybe you mean that for k=2 it s exactly an Hamiltonian path? $\endgroup$ – theantomc Dec 4 '17 at 11:47
  • $\begingroup$ Also, make sure you are doing the reduction the right way. (That is, to show hardness of an unknown problem X, should you reduce X to e.g., Hamiltonian path, or the other way around?) $\endgroup$ – Juho Dec 4 '17 at 11:51
  • $\begingroup$ @Antonio exactly $\endgroup$ – user53923 Dec 4 '17 at 12:12
  • $\begingroup$ @Juho exactly I don't know how do :\ but i know that if want know if my problem is Np-hard i try to reduce my problem X to an another problem Y that is NP-complete. Now I m seeing a Low deegre spanning tree and Bounded-Degree Spanning Tree problem . Unfortunally i don't understand well my first problem, so reduction is more hard to do in this way. $\endgroup$ – theantomc Dec 4 '17 at 12:51
2
$\begingroup$

Hint for part 1: What does it mean when $G$ has a spanning tree where every node has at most 2 neighbors?

Hint for part 2: Suppose you know that it is NP-hard to show that $G$ has a spanning tree where every node has at most 2 neighbors. Can you reduce this problem of at most 2 neighbors to the current problem of at most 5 neighbors?

This post is made out of user53923's comment as I have verified it is useful.

$\endgroup$

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.