91Ó°ÊÓ

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.

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.

(b)

Consider a set of nodes such that$\mathrm{L}⊆\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.

(c)

Consider a set of nodes such that$L⊆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.

(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.

(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}∈\mathrm{V}$ and$w∈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.

(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.