Given the following statements : S1 : The subgraph-isomorphism problem takes…
2014
Given the following statements :
S1 : The subgraph-isomorphism problem takes two graphs G1 and G2 and asks whether G1 is a subgraph of G2 .
S2 : 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
\(\sum_{x \in A} x = \sum_{x \in \overline{A}} x \)
Which of the following is true ?
- A.
S1 is NP problem and S2 is P problem.
- B.
S1 is NP problem and S2 is NP problem.
- C.
S1 is P problem and S2 is P problem.
- D.
S1 is P problem and S2 is NP problem.
Attempted by 56 students.
Show answer & explanation
Correct answer: B
The correct statement is: "S1 is NP problem and S2 is NP problem."
Why each is in NP:
Subgraph-isomorphism (S1): a certificate is a mapping from every vertex of the first graph to a distinct vertex of the second graph. We can verify in polynomial time that every edge of the first graph maps to an edge of the second graph, so the problem is in NP.
Set-partition (S2): a certificate is the proposed subset A. We can compute the sums of A and its complement and check equality in polynomial time, so the problem is in NP.
Why each is NP-hard (brief):
Subgraph-isomorphism is NP-hard because many known NP-hard problems (for example, Clique) can be reduced to it: asking whether a graph contains a k-clique can be phrased as asking whether a k-vertex complete graph is a subgraph of the given graph.
Set-partition is NP-hard (it is a classic NP-complete problem, closely related to subset-sum). There are standard reductions showing its NP-hardness.
Conclusion: both problems are in NP and are NP-hard (so they are NP-complete). Therefore the option that states both problems are NP is correct.