# 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.
Advertisements