The Gateway to Computer Science Excellence
+1 vote
550 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. 
in Graph Theory by Boss (30.1k points)
recategorized by | 550 views

1 Answer

0 votes

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.

by Active (1.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,430 answers
195,211 comments
99,927 users