+1 vote
634 views

Given the following statements :

$S_{1}$ : The subgraph-isomorphism problem takes two graphs $G_{1}$ and $G_{2}$ and asks whether $G_{1}$ is a subgraph of $G_{2}$ .

$S_{2}$ : The set-partition problem takes as input a set $S$ of numbers and asks whether the numbers can be partitioned into two sets $A$ and $\bar{A}=S-A$ such that

$\begin{matrix} \sum x & & \sum x \\ & = & \\ x \in A & & x \in \bar{A} \end{matrix}$

Which of the following is true ?

1. $S_{1}$ is $NP$ problem and $S_{2}$ is $P$ problem.
2. $S_{1}$ is $NP$ problem and $S_{2}$ is $NP$ problem.
3. $S_{1}$ is $P$ problem and $S_{2}$ is $P$ problem.
4. $S_{1}$ is $P$ problem and $S_{2}$ is $NP$ problem.

recategorized | 634 views

S1is NP problem and S2 is NP problem.

The subgraph-isomorphism problem is in NP.this can be proved using Clique Theory. Read NP Problems That can be solved using Clique Theory.
The set partition problem is also on NP.
Let the certificate y be a subset Y of the set S. The verification algorithm A takes the following steps to verify:
(1) check if every number in Y is a number in S
(2) compute the sum of all numbers in the set Y
(3) computer the set S & Y
(4) compute the sum of all numbers in the set S - Y
(5) compare the two numbers obtained in (2) and (4) to see it these two numbers are identical. If yes, then return yes.