# Is maximum-leaves spanning tree np-complete?

How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base?

(maximum-leaves spanning tree: does G have a spanning tree with at least K leaves? )

• Also note its minimum version(minimum leaf spanning tree) is also NP-complete, since it is equivalent to Hamiltonian path problem with $k=2$. – John May 1 '19 at 9:30

The maximum leaf spanning tree(MLSPT) is equivalent to the minimum connected dominating set(MCDS), see here. So we just need to prove MCDS is NP-complete. It's easy to verify that the decision version of MCDS is in NP. Similar to proof of NP completeness of dominating set, we perform a reduction from vertex cover(VC), i.e., we prove that $$VC \le_p MCDS$$:
Given an instance $$(G(V,E),k)$$ of VC we construct an instance $$(G'(V',E'),k)$$ of MCDS as follows: $$G'$$ contains the complete graph on $$V$$, and for each edge $$(u,v)\in E$$, an edge vertex $$x_{uv}$$ is introduced, along with two extra edges $$(x_{uv},u)$$ and $$(x_{uv},v)$$. Formally. we have $$V'=V\cup\{x_{uv}:(u,v)\in E\}$$, $$E' = E\cup\{(x_{u,v},u):(u,v)\in E\}$$. The reduction can obviously be done in polynomial time. Note that any induced subgraph in $$G'$$ is a connected graph.
Let $$S$$ be a vertex cover of $$G$$. For any $$v\in V'\setminus S$$, if $$v\in V$$ then by the definition of vertex cover we know that $$v$$ dominated by $$S$$. If $$v = v_{xy}$$ is an edge vertex of some edge $$(x,y)\in E$$, because $$(x,y)$$ is covered by $$S$$, then $$x\in S$$ or $$y\in S$$, $$v_{xy}$$ is dominated by $$S$$. Thus $$S$$ is a connected dominating set of $$G'$$.
Suppose that $$S$$ is a connected dominating set in $$G'$$. We first observe that for any edge vertex $$v_{xy}$$ in, it can only be dominated by $$x$$ or $$y$$. For any edge vertex $$v_{xy}\in S$$, we replace it with $$x$$. The replacement does not increase the cardinality of $$S$$ and mantains $$S$$'s property of being a dominating set. Now $$S$$ contains no edge vertex, so every edge vertex is dominated by $$S$$, that is to say, every edge in $$G$$ has at least one endpoint in $$S$$. Therefore, $$S$$ is a vertex cover for $$G$$. $$\square$$