HW8 (due just before the final exam)
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)
