12
$\begingroup$

The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$.

I realize that for the case $k=2$, this is the Hamiltonian path problem. However I'm having trouble with cases where $k>2$. I tried thinking about it in the sense that you can add more nodes onto an existing spanning tree where $k=2$ and maybe since the base is NP complete, adding things on will make it NP-complete as well, but that doesn't seem right. I'm self-studying CS and am having trouble with theory, so any help will be appreciated!

$\endgroup$
9
$\begingroup$

The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path.

Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning tree exists. So we can determine the minimum degree of a spanning tree up to an uncertainty of $1$.

$\endgroup$
1
$\begingroup$

My understanding is if you have an algorithm that can solve k-bounded spanning tree problem with any k, you can use that algorithm to solve a special case with k=2, which is essentially a Hamiltonian path. So if your algorithm can achieve polynomial time, then it can be used to solved Hamilton path in polynomial time, which is equivalent to solving any np-complete problems in polynomial time. So the k-bounded spanning tree problem must be np-complete. Note that this is a general idea, not a complete proof.

Also note that being np-complete doesn't mean that there's no polynomial time algorithms that can solve the problem. No one has proven this yet. It only means that all problems that are np-complete are equally hard and if one can be solved in polynomial time then all can be solved in polynomial time.

$\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.