Description
P1) In this exercise we give a polynomial time algorithm to find the minimum vertex cover in a
bipartite graph G = (X, Y, E). Following these steps:
a) Construct a flow network H from the given G just as in the maximum matching algorithm.
b) Given a min cut s − t cut (A, B) in H, construct a vertex cover S ⊆ X ∪ Y of G such that
|S| = cap(A, B)
c) Conversely, given a min vertex cover S ⊆ X ∪ Y of G, construct a s − t cut (A, B) in H
such that cap(A, B) = |S|.
d) Write down the algorithm and use the above argument to prove that it correctly finds the
min vertex cover of G.
P2) A domino is shape like or . Given an n×n table where some of the squares are removed
(in the picture below removed squares are marked with an X), design an algorithm that runs
in time polynomial in n and outputs the minimum number of extra squares to remove from
the table such that we cannot put any domino in the remaining table.
For example, given the table on the left (where 3 squares are removed) you should output 2.
In particular if you remove the two squares marked with X on the right you cannot place any
dominoes on the remaining cells.
X
X
X
⇒
X X
X X
X
P3) 4-Color problem is defined as follows: Given a graph G = (V, E), can we color vertices of G
with 4 colors such that any two neighbors get distinct colors?
5-Color problem is defined as follows: Given a graph G = (V, E), can we color vertices of G
with 5 colors such that any two neighbors get distinct colors?
Prove that 4-Color ≤P 5-Color.
P4) Extra Credit: Prove that the Hamiltonian cycle problem in directed graphs is NP-Complete.
You may use the fact that 3SAT is NP-Complete.
8-1
