Question

Determine which of the following problems are NP-complete and which are solvable in polynomial time. In each problem you are given an undirected graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$, along with:

(a)A set of nodes$\mathbf{L}\mathbf{\subseteq }\mathbf{V}$ , and you must find a spanning tree such that its set of leaves includes the set $\mathbf{L}$.

(b)A set of nodes $\mathbf{L}\mathbf{\subseteq }\mathbf{V}$, and you must find a spanning tree such that its set of leaves is precisely the set $\mathbf{L}$.

(c)A set of nodes$\mathbf{L}\mathbf{\subseteq }\mathbf{V}$ , and you must find a spanning tree such that its set of leaves is included in the set $\mathbf{L}$.

(d)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or fewer leaves.

(e)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or more leaves.

(f)An integer $\mathbf{k}$, and you must find a spanning tree with exactly$\mathbf{k}$ leaves.

Short answer

1. It is solved in polynomial-time.
2. The given problem is NP-complete.
3. The given problem is NP-complete.
4. The given problem is NP-complete.
5. It is related to NP-complete.
6. It is related to NP-complete.

Step-by-step solution

Define NP Complete Problem

A problem that is solved in polynomial time is called an NP Complete Problem. Examples of NP Complete problems are Set Cover problem, Vertex Cover Problem and so on.In order to show that a problem is NP complete, the main task is to show if the problem is solved in polynomial time. If it can be solved then the problem is said to be an NP Complete Problem.

Determine the problem type of (a)

a.

Consider a spanning tree$T$ such that it’s set of leaves is $L$. It remains connected even after deleting the vertices $L$. Therefore, the graph remains connected after deleting $L$and all its incident edges from $G$. The following algorithm identifies a spanning tree$T$ such that it’s set of leaves includes$L$ if such a tree exists:

1. Delete$L$ and all its incident edges from $G$. Consider it as$G$ .

2. Find a spanning tree$T^{\text{'}}$ in$G^{\text{'}}$ .

3. For each vertex$v$ in$L$ , add an edge that connects$v$ to$T^{\text{'}}$ ’.

As a result, it is possible to solve it in polynomial-time.

Check if the problem is NP Complete

(b)

Consider a set of nodes such that$\mathrm{L}\subseteq \mathrm{V}$. It is related to the generalization of RUDRATA$(\mathrm{s},\mathrm{t})$ PATH. Now identify a Rudrata path from$\mathrm{s}$ to$\mathrm{t}$. Assume that$\mathrm{L}=\{\mathrm{s},\mathrm{t}\}$. Then there is a spanning tree with a set of leaves exactly$L$ if and only if there is a Rudrata path from$s$ to$t$ .

Thus, the given problem is NP-complete.

Determine the NP Completeness of (c)

(c)

Consider a set of nodes such that$L\subseteq V$ . It is related to the generalization of RUDRATA$(\mathrm{s},\mathrm{t})$path. Identify a Rudrata path from$\mathrm{s}$to$t$ .Let $\mathrm{L}=\{\mathrm{s},\mathrm{t}\}$. Then there is a spanning tree with a set of leaves included in$L$ if and only if there is a Rudrata path from$s$ to$t$ .

Thus, it is said that the given problem is NP-complete.

Determine the NP Completeness of (d)

(d)

It is related to the generalization of RUDRATA$(\mathrm{s},\mathrm{t})$ -PATH. Assume $k=2$.Then there is a spanning tree with at most k leaves if and only if there is a Rudrata path.

Hence, the given problem is NP-complete.

Determine the NP Completeness of (e)

(e)

This problem is a generalization of 3D-MATCHING. Assume an instance of 3D-matching in the form of a set$W$ of$m$ elements and a set$V$ of triples of$W$ are given. Without loss of generality, each element of$W$ appears in at least one triple. The bipartite graph is constructed here. Define a vertex for each element in$W$ and$V$. There is an edge$(\mathrm{v},\mathrm{w})$ between$\mathrm{v}\in \mathrm{V}$ and$w\in W$if $w$is in triple $v$. Further, there is an edge between any two vertices of $V$.

$\begin{array}{c}\mathrm{k}=\mathrm{n}+\mathrm{m}-\frac{\mathrm{m}}{3}\\ =\mathrm{n}+\frac{2\mathrm{m}}{3}\end{array}$ …..(1)

Consider a spanning tree with$k$ leaves. Each vertex in$V$ is a neighbor of at most three vertices in $W$.If $x$is the number of leaves in$W$ then there are at most$\frac{n-x}{3}$ leaves in$V$ .Therefore $k=n+\frac{2x}{3}$.From (1), $x=m$. All vertices in$W$ must be leaves and$\frac{m}{3}$ non-leaves in$V$ define a 3D matching.

Hence, it is related to NP-complete.

Determine the NP Completeness of (f)

(f)

It is related to the generalization of RUDRATA$(\mathrm{s},\mathrm{t})$ -PATH. Assume$\mathrm{k}=2$ . Then there is a spanning tree with exactly$k$ leaves if and only if there is a Rudrata path. Rudratha path is NP Complete.

Hence, the problem is NP-complete.