What is the definition of the class NP?
AnswerWhat is the definition of an NP-complete problem? (What properties does a problem A need to have in order to be NP-complete?)
AnswerIs the Satisfiability Problem (SAT) known to be NP-complete, or only conjectured to be NP-complete?
AnswerIs it known that P ≠ NP, or is that only conjectured?
AnswerTwo graphs G and H are isomorphic if they have the same number of vertices and it is possible to number their vertices so that the set of edges in G is exactly the same as the set of edges in H. For example, after renumbering the vertices, for each i and j, if G has an edge between vertices i and j, then H also has an edge between i and j, and the other way around. Two isomorphic graphs have the same structure.
The Graph Isomorphism Problem (GIP) is as follows.
Input. Two undirected graphs G and H.
Question. Are G and H isomorphic?
Show that GIP is in NP.
AnswerA subgraph of a graph is obtained by deleting zero or more vertices and zero or more edges. If vertex v is deleted, all edges that are incident on v must also be deleted.
The Subgraph Isomorphism Problem (SIP) is as follows.
Input. Two undirected graphs G and H.
Question. Does there exist a subgraph of G that is isomorphic to H?
Show that SIP is in NP.
AnswerLet HCP by the Hamilton Cycle Problem. Show that HCP ≤p SIP by giving a polynomial time reduction from HCP to SIP.
AnswerAre the results from questions 6 and 7 sufficient to show that SIP is NP-complete?
Answer