Mar 30. NP completeness and Reductions

Recall the following problems for which we do not know a polynomial time algorithm:

  • Clique. Does a graph G have a clique of size \ge k.
  • Independent Set. Does a graph G have an independent set of size \ge k.
  • Vertex Cover. Does a graph G have a vertex cover of size \le k.
  • Satisfiability. Given a boolean formula \phi is there an assignment that satisfies \phi.
  • Hamiltonian Cycle. Does G have a simple cycle containing all the vertices.
  • TSP. Given a weighted complete graph G find a hamiltonian cycle of minimum cost in G.
  • Integer Linear Programming. Does \exists x such that c^\top x \ge k such that Ax \le b and x \in \mathbb{Z}_+.

Note that all the above problems are in the class NP. Recall that the class NP consists of all the languages L such that there is a non-deterministic Turing machine accepts L in polynomial time. That is there is a non deterministic TM M such that for any string x \in L, M accepts x in time polynomial in |x|. Note that the class P \subseteq NP.

Reductions

  • The problem Independent Set polynomial time reduces to Clique. That is if we have a polynomial time algorithm for Clique, then we get a polynomial time algorithm for Independent set. This is because given G, let \bar{G} denote its complement. Then observe that any independent set in G is a clique in \bar{G}. Conversely, Clique also reduces to Independent set by the same reduction.
  • The problem Vertex Cover reduces in polynomial time to Independent set. Given a graph G and a number k, call Independent set on G and |V(G)| - k. Note that the complement of any vertex cover in G is an independent set. Thus there is a vertex cover in G of size \le k if and only if G has an independent set of size \ge |V(G)| - k.
  • The problem 3-SAT reduces Clique. Given a formula \phi construct a graph G_\phi with a vertex for every variable in every clause. Given a variable X_i and X_j in two different clauses if they are compatible. Then the formula \phi is satisfiable if and only if G_\phi has a clique of size m, where m is the number of clauses.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s