Answers to Assignment 4

Question 1:

-The same graph G=(V,E)
-the integer |V|-k

• "yes"->"yes"

Suppose that (G,k) was a "yes" instance to the independent set problem. In other words, there IS an independent set of size k in the graph G. Let S be those vertices in the independent set. And let C = V-S. Now consider the edges of the graph G. For any edge e in E, it must be that one of its endpoints is in C. If this were not true, then both of its endpoints would have been in the independent set, which is impossible. Therefore, C is a vertex cover of G, and also C has size |V|-k. Therefore, the instance (G,|V|-k) is a "yes" instance to the Vertex cover problem.
• "no"->"no"

Suppose that (G,|V|-k) was a "yes" instance to the vertex cover problem. In other words, there IS a vertex cover of size |V|-k in the graph G. Let C be those vertices in the vertex cover, and let S = V-C. Now consider the vertices in S. Let v₁ and v₂ be any two vertices in S. Is it possible that there is an edge between v₁ and v₂? If this were true, then that edge would NOT have an endpoint in C. And this would mean that C was not a vertex cover of G. Therefore, it is impossible that any two vertices in S are neighbours. Therefore S forms an independent set, and it has size k. So a "no" to independent set maps to a "no" instance of vertex cover.

Finding the Maximum matching:

• Convert the Bipartite graph into a network flow
• Use Ford-Fulkerson to find the maximum flow.
• Each edge in the graph which has a positive flow, is now an edge in the maximum matching of G. This was actually done on your assignment 3 and is shown in the text book.
• Let the set of edges in this matching be called M.

Finding the Minimum Vertex Cover

• Suppose that M is a perfect matching, (ie: no vertices are missing). If the graph partition is (A,B), then the vertex cover is simply the vertices on side of the partition, which ever is smallest. In other words, the cover is the min of A or B.
• Otherwise, M is not a perfect matching. An example is shown below where the matched edges are in red.
  
  Let A be one side of the partition that has some vertices which are unmatched. Let the unmatched vertices in A be labelled S. Let U be the set of vertices in A which are reachable from S by alternating paths. And let T be the neighbours of U along edges in M. (See the figure below).
  
• The vertex cover is now (A-S-U)union(T). The size of this vertex cover is exactly the size of M. This is because for each edge in the matching which touches a T vertex, we have exactly one vertex in the cover. Also, for each each in the matching which does NOT touch a T vertex, we have exactly one vertex in the cover in the set (A-S-U). The vertex cover is shown by the yellow vertices in the figure below:
  

Finding the maximum independent set:

• This is easy, just take the vertices which are NOT in the vertex cover. This set is shown in green below. Notice that none of the green vertices are neighbours.
  

Question 2:

Proof.

First we show that PARTITION is in NP. Our certificate will be a subset S of A. We can verify in polynomial time whether S and (A-S) have equal sums (simply by taking the sum of the elements in S and in (A-S)). If these sets have equal sums, then we accept.

Now we show that Partition is NP-complete via a reduction from SUBSET-SUM (defined as: is there a subset of sum k in A?). Let (A,k) be an arbitrary instantance of SUBSET-SUM. We transform this into an instance A' of the PARTITION problem in this way:

• Let m = (the sum of the elements in A).
• Let A' be the set A plus two more elements:
  • a_n+1 = (2m+k), and
  • a_n+2 = (3m-k).

A' can be constructed easily in polynomial time.

I claim that A' is a true instance of PARTITION iff (A,k) is a true instance of SUBSET-SUM. Assume (A,k) is a true instance of SUBSET-SUM. Then there is a subset S of A such that S has size k. Then ((A-S) union {a_n+1}, S union {a_n+2}) is a PARTITION of A'. Now assume that A' is a true instance of PARTITION. Then there exists an equal-weight partition (S₁, S₂) of A'. Notice that the sum of all the elements in A' is 6m. So both a_n+1 and a_n+2 cannot appear in the same subset. Without loss of generality, we say that a_n+1 is in S₁ and a_n+2 is in S₂. Then by construction S₂ - {a_n+2} has sum k (since S₂ has weight 3m). It follows that there is a subset of weight k in A. Therefore, The given reduction reduces SUBSET-SUM to PARTITION, and since SUBSET-SUM is NP-complete, it follows that PARTITION is NP-hard. We have shown that PARTITION is in NP, so PARTITION is NP-complete.

Question 3:

4-SAT is similar to 3-SAT, except that each clause contains exactly 4 distinct literals. Show that 4-SAT is NP-Complete.

Proof.

First we show that 4-SAT is in NP. 4-SAT is just a special case of SAT (i.e. we can use the same certificate for 4-SAT as for SAT), and SAT is in NP, thus 4-SAT is in NP.

Next we show that 4-SAT is NP-complete, by reducing 3-SAT to 4-SAT. Let phi = {C₁, C₂, ..., C_n}} be an arbitrary instance of 3-SAT. Our reduction will go like this. The set of variables in the new instance will be the set of variables in phi, plus one new variable x. To each C_i we add a new literal x. We also add a new clause C_n+1 = {not x, not x, not x, not x}. Call this new instance phi'. This construction can be easily computed in polynomial time.

We claim that phi' is in 4-SAT iff phi is in 3-SAT. Assume phi' is in 4-SAT. Then C_n+1 must be satisfied. Therefore x must be assigned to false, therefore the fourth literal of each clause in phi' must be false. Therefore there must be an assignment to the remaining variables such that for each clause C_i, at least one of the first three literals is satisfied. It is easy to see that this is only possible if the original 3-SAT instance phi' is satisfiable. Now assume that the 3-SAT instance phi is satisfiable by some assignment. Then we can satisfify phi' by using the satisfying assignment to phi and by setting x to false. Thus phi' is in 4-SAT iff phi is in 3-SAT, and the claim is proven.

Question 4: