NP completeness proof of a spanning tree problem
-
16-10-2019 - |
문제
I am looking for some hints in a question asked by my instructor.
So I just figured out this decision problem is $\sf{NP\text{-}complete}$:
In a graph $G$, is there a spanning tree in $G$ that contain an exact set of $S=\{x_1, x_2,\ldots, x_n\}$ as leafs. I figured out we can prove that it is $\sf{NP\text{-}complete}$ by reducing Hamiltonian path to this decisions problem.
But my instructor also asked us in class:
would it also be $\sf{NP\text{-}complete}$ if instead of "exact set of $S$", we do
"include the whole set of $S$ and possibly other leafs" or "subset of $S$"
I think "subset of S" would be $\sf{NP\text{-}complete}$, but I just can't prove it, I don't know what problem I can reduce it to this. As for "include the set of $S$..." I think it can be solved in polynomial time.
해결책
In short, your guesses are correct. For the purpose of this answer, let’s call the three problems in question as follows:
- Equality version: Given a graph $G = (V, E)$ and a set $S \subseteq V$, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is equal to $S$. As you stated, this is NP-complete by a reduction from the Hamiltonian path problem.
- Subset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a subset of $S$.
- Superset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a superset of $S$.
To prove that the subset version is NP-complete, you can still reduce the Hamitonian path problem to it. Try to modify the proof of the NP-completeness of the equality version.
To prove that the superset version can be solved in polynomial time, try to find a necessary and sufficient condition for such a tree $T$ to exist.
Both versions (as well as some other problems about spanning trees) are studied in [SK05]. But I guess that it is better if you try to solve the problems by yourself before looking at the proofs in the paper, because looking at the paper can be a big spoiler. Unfortunately I had looked at the paper before trying to find a polynomial-time algorithm for the superset version!
[SK05] Mohammad Sohel Rahman and Mohammad Kaykobad. Complexities of some interesting problems on spanning trees. Information Processing Letters, 94(2):93–97, April 2005. [doi] [author copy]
다른 팁
These hints weren't enough to get me to a solution for the superset of S problem - though the hints are helpful and correct. This is my train of thought that got me to a solution.
What happens if you remove all the vertices in S from G, (V-S), and then find a spanning tree T with DFS? If there are any yet unconnected vertices in G, say v1; what does that say about the role of at least one of the vertices in S that was removed? That it lies in the path to v1 from some vertex that is presently in the spanning tree. Thus, it can't be a leaf (since leaves have no children). If there are no unconnected nodes, that means every vertex in S can be a leaf provided it has an edge leading to the spanning tree. Vertices in S that only connect to other vertices in S of course won't have a connection to the spanning tree and would violate the condition. So, there are two cases to check for:
- If all nodes not in S are connected after removing S from G and finding a spanning tree
- If each node in S can be connected directly to the spanning tree.