NP: Graph problems

PDF of Eric’s handwritten notes are here.

In this last lecture we took for granted that SAT is NP-Complete, and then we used this fact to show that 3-SAT is NP-Complete.  Now we’ll build on the NP-completeness of 3-SAT to prove that a few graph problems, namely, Independent Set, Clique, and Vertex Cover, are NP-Complete.

The first problem we’ll consider is the independent set problem.  Let’s first recall the definition of an independent set.

Definition: Independent Set:

For an undirected graph $G = (V, E)$, $S \subset V$ is an independent set if for all $x, y \in S$, we have $(x,y) \notin E$.
In other words, no edge is contained in $S$.

Small independent sets are trivial to find, e.g., the empty set or a single vertex.  The challenge is to find a large independent set.  For the Max-Independent-Set problem in which we find an independent set of maximum size, we can’t show that’s in NP, unless P=NP, because we can’t verify that a set is of maximum size.  Hence we have an extra input parameter $g$ and we look for an independent set of size $\geq g$.

Definition: Independent-set Problem:

• Input: Undirected graph $G = (V,E)$ and goal $g$.
• Output: Independent Set $S \subset V$ where $|S| \geq g$ if one exists;
NO otherwise.

Proof:

a) Independent-set $\in$ NP: Given input $G, g$ and solution $S$, we
consider all pairs $x, y \in S$ and check that $(x, y) \notin E$.  This takes $O(n^2)$ time to consider all pairs in $S$ and $O(n)$ time for each pair to check that it is not an edge.  Finally, in $O(n)$ time we check that $|S| \geq g$.

b) 3-SAT $\rightarrow$ Independent-set

Assume there is a poly-time algorithm for the independent-set problem, and we’ll use this algorithm as a black-box to create an algorithm for the 3-SAT problem.

Consider 3-SAT input $f$ with $n$ variables $x_1, x_2, \dots, x_n$
and $m$ clauses $C_1, C_2, \dots, C_m$, where each clause has size $\leq 3$.

We will create a graph $G$ based on $f$.  Formula $f$ has $m$ clauses so we will set $g = m$.

The vertices of $G$ will correspond to literals of $f$, though there will potentially be many vertices corresponding to the same literal.  If all clauses are of size exactly 3 then we will have $3m$ vertices in $G$.  Let us define it precisely.

For a clause $C = (a_1 \vee a_2 \vee a_3)$ for literals $a_1, a_2, a_3$, create 3 vertices corresponding to $a_1, a_2, a_3$ and put all 3 edges between them to make them a triangle. In general, if clause $C$ has size $i\leq 3$ then add $i$ vertices corresponding to the literals in $C$ and add the complete graph between these $i$ vertices.

Note, any independent set of $G$ can include at most one of the $i$ vertices for each clause $C$.  And hence to obtain an independent set of size $\geq g$ where $g=m$ it will need to include exactly one per clause “gadget”.

For each variable $x_i$, add an edge between all vertices corresponding to $x_i$ and all vertices corresponding to $\overline{x_i}$. These edges ensure that an independent-set $S$ does not include both $x_i$ and $\overline{x_i}$, and hence $S$ corresponds to a valid assignment for $f$.

Combining these two properties, we know that to get $|S| = g = m$, we need exactly one vertex per clause, and hence a solution to the independent-set problem on the graph $G$ corresponds to a satisfying assignment of $f$.  Let us formalize this.

Claim: $f$ has a satisfying assignment $\leftrightarrow$ $G$ has an independent set of size $\geq g$.

Proof:

($\Rightarrow$): Consider a satisfying assignment for $f$. For each clause $C$, at least one of the literals in $C$ is satisfied. Choose one of these satisfied literals and include its corresponding vertex in $S$. Hence, $|S| = m = g$.
By construction, $S$ includes exactly one vertex per clause so no edges within a clause’s gadget are covered by $S$.  Moreover, since we started from an assignment for the variables $x_1,\dots,x_n$ then $S$ does not include opposing literals, so no edges between opposite literals are covered. Hence, $S$ is an independent set.

($\Leftarrow$): Take an independent set $S$ of size $\geq g$. For each vertex in $S$ set the corresponding literal to $T$, we will prove this gives a satisfying assignment.   Since there are edges between vertices corresponding to opposite literals, $S$ does not contain vertices corresponding to opposite literals and so this assignment from $S$ will not set both literals $x_i$ and $\overline{x_i}$ to $T$; hence, it is a valid assignment.  Moreover, since $|S|\geq g$ and since there is a complete graph for each clause’s gadget, the set $S$ has exactly one vertex per clause’s gadget.  This gives at least one satisfied literal per clause and hence we have a valid assignment that satisfies $f$.

Next we’ll consider the clique problem.  Here is the definition of a clique.

Definition: Clique:

Clique: For an undirected graph $G = (V, E)$, $S \subset V$ is a clique if for all $x, y \in S$, we have $(x,y) \in E$.
In other words, $S$ is a fully connected subgraph.

The challenge is to find a large clique.

Definition: Clique Problem:

• Input: Undirected graph $G = (V,E)$ and goal $g$.
• Output: Clique $S \subset V$ where $|S| \geq g$ if one exists;
NO otherwise.

Proof:

a) Clique $\in$ NP: Given input $G, g$ and solution $S$, check for all pairs $x, y \in S$ that $(x, y) \in E$; this takes $O(n^2)$ time.  Then, check $|S| \geq g$ which takes $O(n)$ time.

b) Independent Set $\rightarrow$ Clique

Key idea: Clique is opposite of independent set.
For a graph $G = (V, E)$, denote its “opposite” graph by: $\overline{G} = (V, \overline{E})$ where $\overline{E} = \{(x,y): (x,y) \notin E\}$. In other words, $(x, y) \notin E \leftrightarrow (x, y) \in \overline{E}$.
Observe that: $S$ is an independent set in G $\leftrightarrow$ $\overline{S}$ is a clique in $\overline{G}$.

Now we can show Independent set $\rightarrow$ Clique:
Given $G = (V,E)$ and $g$ as input for the independent set problem, let $\overline{G}$ and $g$ be the input to the clique problem.
If we get a solution $S$ for Clique then return the same $S$ as the solution to the original independent set problem.  If we get NO, then we return NO for the independent set problem.

Definition: Vertex Cover:

For an undirected graph $G = (V, E)$, $S \subset V$ is a vertex cover if it covers every edge in the following sense: for all $(x,y) \in E$, either $x \in S$ and/or $y \in S$.

The set $S=V$ is a trivial vertex cover, and hence the challenge is to find a small vertex cover.

Definition: Vertex Cover Problem:

• Input: Undirected graph $G = (V,E)$ and goal $b$
• Output: VC $S \subset V$ where $|S| \leq b$ if one exists; NO otherwise

Proof:

a) Vertex Cover $\in$ NP: Given input $G, g$ and solution $S$, for every edge $(u,v)\in E$ of $G$, check that at least one of $u$ and $v$ are in $S$; this takes $O(m)$ time.  We then check that $|S| \leq b$ which takes $O(n)$ time.

b) Independent Set $\rightarrow$ Vertex Cover.

Claim: For any undirected graph $G=(V,E)$, $S$ is a vertex cover $\leftrightarrow$ $\overline{S}$ is an independent set.

Proof:

($\Rightarrow$): Consider a vertex cover $S$ where $|S|\leq b$. For each $(x,y) \in E$$x \in S$ and/or $y \in S$. Hence, at most one of $x, y$ is in $\overline{S}$. So no edge has both endpoints in $\overline{S}$, which means $\overline{S}$ is an independent set.

($\Leftarrow$): Take an independent set $\overline{S}$. For $(x,y) \in E$, at most one of $x,y$ is in $\overline{S}$. So at least one of $x,y$ is in $S$, which means $S$ covers every edge, and hence $S$ is a vertex cover.

Independent Set problem $\rightarrow$ Vertex Cover problem:
Consider input $G, g$ for independent set problem.  Let $G, b = |V|-g$ be the input for the vertex cover problem.  We know that $G$ has an independent set of size $\geq g$ $\leftrightarrow$ $G$ has a vertex cover of size $\leq b$.

If we get solution $S$ for vertex cover, then wen return $\overline{S} = V-S$ as the solution to the original independent set problem.
If we get NO solution for VC, then we return NO for IS.