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?

Improve this question
$\endgroup$
5
  • 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
    Commented Dec 4, 2017 at 10:35
  • 1
    $\begingroup$ @user53923 maybe you mean that for k=2 it s exactly an Hamiltonian path? $\endgroup$
    – theantomc
    Commented Dec 4, 2017 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
    Commented Dec 4, 2017 at 11:51
  • $\begingroup$ @Antonio exactly $\endgroup$
    – user53923
    Commented Dec 4, 2017 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
    Commented Dec 4, 2017 at 12:51

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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