Description
1 – Define SUBGRAPH ISOMORPHISM (SI) problem as follows : Given two undirected graphs G and H, is G a subgraph of H ? (G is a subgraph of H if for the set {v1,v2, …,vn} of all nodes of G there are corresponding nodes {u1,u2, …, un} of H such that {vj,vi} is an edge in G iff {uj,ui} is an edge in H ). Prove that SI is an
NP-complete problem.
2 – Define INTEGER PROGRAMMING (IP) problem as follows : Given m equations :
-
j=1,n aij xj = bi , i=1, …, m
in n variables xj with integer coefficients aij and bj , are there solutions with xj equal to 1 or 0 for each j ? Prove that IP is an NP-complete problem.
3 – Define 3-COLORING (3C) problem as follows : Given an undirected graph can its vertices colored with three colors such that no two adjacent nodes have the same color. Prove that 3C is an NP-complete problem (Hint : Use a polynomial reduction to 3SAT)
