2
$\begingroup$

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? )

$\endgroup$
  • $\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 Ma May 1 at 9:30
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.