IMG_0336.jpeg

# Lecture 12: Feb 26, 2024 ## Recap Last time, we discussed * NP completeness * Circuit SAT is NP-Complete * 3-SAT is NP-Complete This time, we will discuss * More NP-Completeness * Clique * Independent Set * Vertex Cover ## More NP-Completeness ### Cliq...

# Lecture 12: Feb 26, 2024 ## Recap Last time, we discussed * NP completeness * Circuit SAT is NP-Complete * 3-SAT is NP-Complete This time, we will discuss * More NP-Completeness * Clique * Independent Set * Vertex Cover ## More NP-Completeness ### Clique #### Definition A clique in an undirected graph $G = (V, E)$ is a subset of vertices $V' \subseteq V$, such that every pair of vertices in $V'$ is connected by an edge. In other words, for all $u, v \in V'$, $(u, v) \in E$. **CLIQUE**: Given a graph $G$ and an integer $k$, does $G$ contain a clique of size $k$? #### Theorem CLIQUE is NP-Complete. #### Proof 1. CLIQUE $\in$ NP: Given a graph $G = (V, E)$ and an integer $k$, we can verify in polynomial time whether there is a subset $V' \subseteq V$ of size $k$ that forms a clique. 2. Reduction: We will show that 3-SAT $\le_p$ CLIQUE. Given a 3-SAT formula $\phi$ with $k$ clauses, we construct a graph $G$ as follows: * For each clause $C_i$ in $\phi$, create a vertex in $G$ corresponding to each literal in $C_i$. * Add an edge between two vertices if: * They belong to different clauses, and * The literals they represent are not negations of each other. Now, $G$ has a clique of size $k$ if and only if $\phi$ is satisfiable. ##### Example $\phi = (x \lor y \lor z) \land (\bar{x} \lor \bar{y} \lor w) \land (\bar{w} \lor y \lor z)$ Clauses: $C_1 = (x \lor y \lor z)$ $C_2 = (\bar{x} \lor \bar{y} \lor w)$ $C_3 = (\bar{w} \lor y \lor z)$ ###### Graph G: * Vertices: $x, y, z, \bar{x}, \bar{y}, w, \bar{w}, y, z$ * Edges: Connect vertices from different clauses that are not negations of each other. For example: * $(x, \bar{y})$, since $x$ and $\bar{y}$ are not negations and are in different clauses. * $(x, w)$, since $x$ and $w$ are not negations and are in different clauses. * $(y, \bar{x})$, since $y$ and $\bar{x}$ are not negations and are in different clauses. * $(y, w)$, since $y$ and $w$ are not negations and are in different clauses. * $(z, \bar{x})$, since $z$ and $\bar{x}$ are not negations and are in different clauses. * $(z, \bar{y})$, since $z$ and $\bar{y}$ are not negations and are in different clauses. * $(z, w)$, since $z$ and $w$ are not negations and are in different clauses. * $(\bar{x}, y)$, since $\bar{x}$ and $y$ are not negations and are in different clauses. * $(\bar{x}, z)$, since $\bar{x}$ and $z$ are not negations and are in different clauses. * $(\bar{y}, \bar{w})$, since $\bar{y}$ and $\bar{w}$ are not negations and are in different clauses. * $(\bar{y}, y)$, since $\bar{y}$ and $y$ are not negations and are in different clauses. * $(\bar{y}, z)$, since $\bar{y}$ and $z$ are not negations and are in different clauses. * $(w, y)$, since $w$ and $y$ are not negations and are in different clauses. * $(w, z)$, since $w$ and $z$ are not negations and are in different clauses. * $(y, \bar{w})$, since $y$ and $\bar{w}$ are not negations and are in different clauses. * $(z, \bar{w})$, since $z$ and $\bar{w}$ are not negations and are in different clauses. A clique of size 3 in $G$ corresponds to a satisfying assignment for $\phi$. For instance, choosing $x$ from $C_1$, $w$ from $C_2$, and $y$ from $C_3$ forms a clique, and setting $x = TRUE, w = TRUE, y = TRUE$ satisfies $\phi$. ### Independent Set #### Definition An independent set in an undirected graph $G = (V, E)$ is a subset of vertices $V' \subseteq V$ such that no two vertices in $V'$ are connected by an edge. In other words, for all $u, v \in V'$, $(u, v) \notin E$. **INDEPENDENT-SET**: Given a graph $G$ and an integer $k$, does $G$ contain an independent set of size $k$? #### Theorem INDEPENDENT-SET is NP-Complete. #### Proof 1. INDEPENDENT-SET $\in$ NP: Given a graph $G = (V, E)$ and an integer $k$, we can verify in polynomial time whether there is a subset $V' \subseteq V$ of size $k$ that forms an independent set. 2. Reduction: We will show that CLIQUE $\le_p$ INDEPENDENT-SET. Given a graph $G = (V, E)$ and an integer $k$, we construct a graph $G' = (V, E')$ such that $E'$ contains all the edges that are *not* in $E$. In other words, $G'$ is the complement graph of $G$. $G$ has a clique of size $k$ if and only if $G'$ has an independent set of size $k$. ### Vertex Cover #### Definition A vertex cover in an undirected graph $G = (V, E)$ is a subset of vertices $V' \subseteq V$ such that every edge in $E$ is incident to at least one vertex in $V'$. In other words, for all $(u, v) \in E$, either $u \in V'$ or $v \in V'$ (or both). **VERTEX-COVER**: Given a graph $G$ and an integer $k$, does $G$ contain a vertex cover of size $k$? #### Theorem VERTEX-COVER is NP-Complete. #### Proof 1. VERTEX-COVER $\in$ NP: Given a graph $G = (V, E)$ and an integer $k$, we can verify in polynomial time whether there is a subset $V' \subseteq V$ of size $k$ that forms a vertex cover. 2. Reduction: We will show that INDEPENDENT-SET $\le_p$ VERTEX-COVER. Given a graph $G = (V, E)$ and an integer $k$, we want to find a vertex cover of size $|V| - k$. $S$ is an independent set of size $k$ if and only if $V - S$ is a vertex cover of size $|V| - k$.