Classic NPC Problems

3-SAT

Given a CNF formula $\phi$, is there a satisfying assignment?

instance $s$:

$\phi = (\overline{x_1} \lor x_2 \lor x_3) \land (x_1 \lor \overline{x_2} \lor x_3) \land (\overline{x_1} \lor x_2 \lor x_4)$

certificate t:

$x_1 = true, x_2 = true, x_3 = false, x_4 = false$

Set Cover Problem

Given a set $U$ of elements, a collection of subsets of $U$, $S_1, S_2, S_3, ..., S_m$, and an integer $K$, does there exist a collection of size $\leq K$ whose union is equal to $U$?

Example:

$U = \{1, 2, 3, 4, 5, 6, 7\}$

$S_1 = \{3, 7\}, S_2 = \{2, 4\}, S_3 = \{3, 4, 5, 6\}, S_4 = \{1\}, S_5 = \{1, 2, 6, 7\}$

Let $K = 2$. Yes, we have $S_3$ and $S_5$.

Vertex Cover Problem

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Finding a minimum vertex cover is NP-hard. The decision version is NP-complete. To formally state this,

given an undirected graph $G = (V, E)$, a vertex cover of $G$ is a subset $V' \in V$ such that, for every edge $(u, v) \in E$, we have either $u \in V'$ or $v \in V'$. Is there a vertex cover such that $|V'| \leq K$ ?

VC is a special case of set cover. Here is the reduction from vertex cover. So set cover is at least as hard as VC.

Let $K = K, U = E, S_v = \{e \in E : e \; incident \; to \; v \}$, then set cover of size $\leq K$ iff vertex cover of size $\leq K$.

Clique Cover Problem

Independent Set Problem

In a graph, an independent set is a set of vertices such that no two of which are adjacent. A maximum independent set is an independent set of largest possible size for a given graph G. Again, max independent set is NP-hard. The decision version of independent set is NPC.

Reference

• List of NPC Problems

• Proof VC is NPC