Question

The input to SPANNINGTREEWITHKLEAVES is a graph G and an integer K. The question asked by SPAN NINGTREEWITHKLEAVES is whether G has a spanning tree with exactly K leaves. Problem 3. Show that SPANNINGTREEWITIIKLEAVES is NP-complete. Hint: There is a simple polynomial time reduction from HAMILTONIANPATH to SPANNINGTREEWITHKLEAVES.

Answer 1

NP-completeness Theorem (Lemke). A maximum leaf spanning tree problem for cubic graphs is NP-complete. Proof. So we consider the following decision problem associated with the maximum leaf spanning tree problem: INSTANCE: A cubic graph G and an integer number k. QUESTION: Does G posses a spanning tree with at least k leaves? Instead of this decision problem let us consider more specic decision problem: INSTANCE: A cubic graph G. QUESTION: Does G posses a spanning tree with at least |V (G)| 2 + 1 leaves? The last question has an equivalent reformulation for cubic graphs: EQUIVALENT QUESTION: Does G posses a spanning tree with no vertices of degree two? Remark 1. Indeed why this is equivalent reformulation? Proof. Notations. a1 := number of vertices in spanning tree T with degree 1. a2 := number of vertices in spanning tree T with degree 2. a3 := number of vertices in spanning tree T with degree 3. N := number of vertices in T. We know that a1 + a2 + a3 = N as T is a spanning tree and contains all the vertices of G. Also we know that a1 + 2a2 + 3a3 = 2(N ? 1) as every tree on N vertices contains exactly N ? 1 edges. So subtract the second equality from the doubled rst one we get a1 ? a3 = 2. Suppose now T has at least |V (G)| 2 + 1 leaves. It means a1 ? |N| 2 + 1 and so by thethird equality a3 ? |N| 2 ? 1. And as a1 + a2 + a3 = N we get a2 = 0. It means that T has no vertices of degree two. In the other direction. Let T has no vertices of degree two then a2 = 0 and so 3a1 + 3a3 ? a1 ? 3a3 = 3N ? 2(N ? 1). And we get a1 = N 2 + 1. Let us return to the proof of theorem. The proof will be by reduction of known NP-complete problem EXACT COVER BY 3-SETS [4] to ours. The EXACT COVER BY 3-SETS is as follows: INSTANCE: Positive integers n and m, subsets S1, S2, ..., Sm of {1, 2, ...., n}, with |Si | = 3 for all i ? {1, 2, ..., m}. QUESTION: Is there a subset Q ? {1, 2, ..., m} such that S i?Q Si = {1, 2, ..., n} and ?i1, i2 ? Q, i1 6= i2 ? Si1 ? Si2 =

Answer 2

Now we shall show that this is NP-complete, by reduction from HAMILTONIAN CYCLE. Given graph G, for which we wish to check if a Hamiltonian cycle exists, we a construct a MINIMUM LEAF-SPANNING-TREE problem that asks if a spanning tree with k = 2 or fewer leaves exists in a modified graph G0 . G0 is constructed as follows : G0 will have all the nodes and edges that G has, but we will also choose an arbitrary node v in G, and create a duplicate v 0 . v 0 is a duplicate of v in the sense that for every edge {v, u} in G, {v 0 , u} will be an edge in G0 . We also add two extra nodes w and w 0 with edges {w, v} and {w 0 , v0} that connect them to v and v 0 respectively. Note that the reduction is polynomial time. We have to show that G has a Hamiltonian cycle if and only if G0 has a spanning tree with 2 or fewer leaves. To see the if part, notice that is G has a Hamiltonian cycle, then there exists a path from v to v that covers all the vertices. Since v 0 is a duplciate of v, this implies a path from v to v 0 in G0 , and we can add the two additional edges to make a path from w to w 0 that visits all the nodes in the graph G0 . This path is a spanning tree with only 2 leaves, w and w 0 . So a Hamiltonian cycle in G implies a spanning tree in G0 with 2 leaves. To see the other direction, assume that G0 has a spanning tree T with 2 or fewer leaves. Assume that (we will show later) T has a simple path from w to w 0 that covers all the vertices in G0 . From this path, we can remove the starting edge {w, v} and the ending edge {v 0 , w0}, then we have a simple path from v to v 0 . Since v 0 is a duplicate of v, this implies a simple path which starts and ends in v and visits all the vertices in G. This is a Hamiltonian cycle in G. The only thing that is left to be proven is that, if G0 has a spanning tree T, then there must be a simple path from w to w 0 that visits all the vertices in G0 . If T is a spanning tree, then there must be a unique path from w to 4w 0 in T. We can show that if this path does not include all the vertices in G0 then T must have atleast 3 leaves. Suppose that there is a node z that is not in the path from w to w 0 in T. The path from w to w 0 must diverge from the path from w to z in T. Let it diverge at x. Clearly, x has degree atleast 3 in T, and if we remove x, then we get 3 distinct components of T, and hence 3 leaves. This contradicts the fact that T has only 2 leaves, and hence there is no such z which the path from w to w 0 does not include.