14 NP-Complete proofs

S. Sridhar

This module 35 focuses on proving NP-Complete problems. The module extends previous module by providing proof outlines for NP-Complete problems. The module also discusses proofs for some problems like TSP, Clique, vertex cover and sum of subsets. The objectives of this module are

 

•       To Understand proof of NP-C

•        To understand proof of TSP problem

•         To understand proof of Clique, Vertex cover problem and Sum of Subsets

 

Computational Complexity

 

There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory [2,3]. Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm.

 

NP-Complete Problems

 

NP-Complete (or NPC) problems are a set of problems that are well connected. A problem x that is in NP, if any one finds an polynomial time algorithm even for one problem, it implies that polynomial time algorithm for all NP-Complete problems. In other words: Problem x is in NP, then every problem in NP is reducible to problem x. Let us present the overview of reductions first.

 

Reductions

 

Reduction algorithm reduces a problem to another problem. There are two types of reduction. One is called Turing reduction and another is called Karp reduction. They are explained in module 34. Reductions form the basis of NP-Complete proofs. The proof of NP-Complete problems starts with reducing a well-known NP-Complete problem to a problem for which NP-Complete proof is sought. This reduction should take place in polynomial time. Then the equivalence of the problems is justified. Let us discuss some basic NP-Complete proofs now:

 

Traveling Salesman Problem

 

Let us consider giving NP-Complete proof for travelling salesman (TSP) problem. One can consider NP-Complete proof outline.

 

1.  Take a well-known NP-Complete problem and reduce that to the given problem for which proof is sought and prove that the reduction is done in polynomial time.

3.  Argue that the given problem is as hard as the well known NP-Compete problem.

 

To prove TSP as NP-Complete, take a well known problem Hamiltonian Cycle Problem. It is a well known NP-Complete problem

 

 

1.      The first step is to prove that Hamiltonian circuit is a NP-Complete problem. One can guess many sequences of cities as certificates. The verification algorithm is possible if a tour can be guessed which is of length of k. This verification can be done in polynomial time. Therefore, Hamiltonian cycle is a NP-Complete problem.

2.  In step 2, Hamiltonian cycle can be reduced to Traveling Salesman problem in polynomial time. This is done by taking arbitrary G instance of Hamiltonian cycle and construct G’ and bound k such that G has Hamilton cycle iff G’ has a tour of length k

 

 

 

Assign k =n. the graph G has a Hamiltonian cycle iff G’ has a tour of cost at most 0. If the graph G has a Hamiltonian cycle h, then all the edges belongs to E and thus has a cost of at most 0 in G’. Thus h is a tour in G’ with cost of 0.

 

 

Conversely, suppose graph G’ has a tour h’ of cost 0. Since the cost of the tour is 0, each edge of the tour must have cost of 0. Therefore, h’ contains only edges in E. Therefore, one can conclude that h’ is a Hamiltonian cycle in graph G [3]. Therefore, one can conclude that TSP is as hard as Hamiltonian cycle.

 

Clique problem

 

The NP-Complete proof for Clique problem can be give as per the proof outline. Let us formally, state the clique problem as follows:

 

Given a Graph G = (V,E) and a positive integer k, Does G contain a clique of size k? Clique k is a complete subgraph of graph G on k vertices.

 

For example, for the sample graph shown in Fig. 1, the clique is shown in Fig. 2.

It can be observed the subgraph of three vertices shown in Fig. 2. Is the clique for the sample graph shown in Fig. 1.

 

 

  1. In step 1, a well-known NP-Complete problem, SAT (Formula Satisfiability problem) is chosen. One can recollect from module 34, Satisfiability problem can be given as follows:

 

 

Given a Boolean formula, determine whether this formula is satisfiable or not.  The Boolean

 

formula may have a literal : x1 or x1 , a clause C like x1 v x2 v x3 and formula be in the conjunctive normal form as C1& C2 & … & Cm . It can be observed that there would be m-clauses.

 

The reduction from SAT problem to clique problem is given as follows:

Construct a graph G = (V,E) where V = 2n literals and edge as

 

  1. In step 2, one can observe that F is satisfiable iff G has a clique of size m
  2. In step 3, one can argue that a clique of m corresponds to assignment of true to m literals in m different clauses. It should also be observed that
  • An edge is between only non-contradictory nodes. Hence, f is satisfiable iff there is non-contradictory assignment of true to m literals.
  • This is possible iff G has a clique of size m.

Therefore, one can conclude that Clique problem is NP-Complete.

 

 

Vertex Cover

 

Vertex cover is discussed in module 32 and module 33. One can recollect that the vertex cover problem can be stated as follows:

Given a graph G = (V,E) and a positive integer k, Find a subset C of size k such that each edge in E is incident to at least one vertex in C

Solution

 

No. Because, Edges (4, 5), (5, 6) and (3, 6) are not covered by it . So, the idea is to cover all edges of the given graph, by picking the extra vertices 4 and 3 so that all edges are covered. The idea is thus to pick a minimum set of vertices so as to cover the graph. The proof for vertex cover can be given based on [4] as follows: First a Formula SAT is chosen and the graph is constructed using the following rules.

 

Thus one can conclude that vertex cover proble m is NP-Complete.

 

Summary

 

One can conclude from this module 35 that

  • NP-Complete proof can be given by reducing a well known NP-Complete problem to the given problem.
  • Traveling Salesman is proven NP complete by reducing Hamiltonian problem to TSP
  • Clique problem is NP-Complete
  • Vertex Cover problem is NP-Complete

 

References:

 

  1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.
  2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
  3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.
  4. M.H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific Press, Singapore, 1999.