23
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you elaborate why you think the one version can be solved in polynomial time? $\endgroup$
    – Raphael
    Mar 27, 2012 at 7:08
  • $\begingroup$ @pad: "My instructor asked in class" is not an assignment but a puzzle. Also, see this meta discussion on the homework tag. $\endgroup$
    – Raphael
    Mar 27, 2012 at 7:09

2 Answers 2

15
$\begingroup$

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]

$\endgroup$
2
  • $\begingroup$ Good to see you over here! Note that we have MathJax here, too. $\endgroup$
    – Raphael
    Mar 27, 2012 at 14:12
  • 1
    $\begingroup$ Thanks for the guidance!! I wish I read this before I went to class though, he spoiled it today haha. In case anyone interested the superset version polynomial algorithm, another hint is constructing a new graph with V\L. $\endgroup$
    – initialize
    Mar 27, 2012 at 21:26
0
$\begingroup$

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:

  1. If all nodes not in S are connected after removing S from G and finding a spanning tree
  2. If each node in S can be connected directly to the spanning tree.
$\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.