prueba de un problema NP completo árbol de expansión

Question

Estoy buscando algunas pistas en una pregunta formulada por mi instructor.

Así que acabo de descubrir este problema de decisión es $ \ sf {NP \ text {-} completa} $:

En un gráfico $ G $, ¿hay un árbol de expansión de $ G $ que contiene un conjunto exacto de $ S = \ {x_1, x_2, \ ldots, x_n \} $ como hojas. Me di cuenta de que podamos probar que es $ \ sf. {NP \ text {-}} $ completa mediante la reducción camino de Hamilton a este problema decisiones

Pero mi instructor también nos preguntó en clase:

sería también $ \ sf {NP \ text {-}} $ completa si en lugar de "conjunto exacto de $ S $", que hacemos

"incluye todo el conjunto de $ S $ y, posiblemente, otras hojas" o "Subconjunto de S $ $"

Creo "subconjunto de S" sería $ \ sf {NP \ text {-}} $ completa, pero simplemente no puede probarlo, no sé qué problema puedo reducirlo a esto. En cuanto a "incluir el conjunto de $ $ S ..." Creo que se puede resolver en tiempo polinómico.

Answer 1

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]

Answer 2

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.