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? )
1
-
$\begingroup$ Also note its minimum version(minimum leaf spanning tree) is also NP-complete, since it is equivalent to Hamiltonian path problem with $k=2$. $\endgroup$– Mengfan MaMay 1, 2019 at 9:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$
