Lecture 7

Known NP-Complete Problems

• SAT and 3-SAT
• Vertex Cover
• Independent Set

How to show a problem $L$ is NP-Complete

• Show $L \in$ NP
  • Give a polynomial time certificate
  • Give a polynomial time verifier
• Show $L$ is NP-Hard: for some known NP-Complete problem $K$, show $K \leq_p L$
  • Construct a mapping $\phi$ from instance in $K$ to instance in $L$, given an instance $k\in K$, $\phi(k)\in L$.
  • Show that you can compute $\phi(k)$ in polynomial time.
  • Show that $k \in K$ is true if and only if $\phi(k) \in L$ is true.

Example 1: Subset Sum

Input: A set $S$ of integers and a target positive integer $t$.

Problem: Determine if there exists a subset $S' \subseteq S$ such that $\sum_{a_i\in S'} a_i = t$.

We claim that Subset Sum is NP-Complete.

Step 1: Subset Sum $\in$ NP

• Certificate: $S' \subseteq S$
• Verifier: Check that $\sum_{a_i\in S'} a_i = t$

Step 2: Subset Sum is NP-Hard

We claim that 3-SAT $\leq_p$ Subset Sum

Given any $3$-CNF formula $\Psi$, we will construct an instance $(S, t)$ of Subset Sum such that $\Psi$ is satisfiable if and only if there exists a subset $S' \subseteq S$ such that $\sum_{a_i\in S'} a_i = t$.

How to construct $\Psi$?

Reduction construction:

Assumption: No clause contains both a literal and its negation.

3-SAT problem: $\Psi$ has $n$ variables and $m$ clauses.

Need to: construct $S$ of positive numbers and a target $t$

Idea of construction:

For 3-SAT instance $\Psi$:

• At least one literal in each clause is true
• A variable and its negation cannot both be true

$S$ contains integers with $n+m$ digits (base 10)

where $p_i$ are representations of variables that are either $0$ or $1$ and $q_j$ are representations of clauses.

For each variable $x_i$, we will have two integers in $S$, called $v_i$ and $\overline{v_i}$.

• For each variable $x_i$, both $v_i$ and $\overline{v_i}$ have digits $p_i=1$. all other $p$ positions are zero

• Each digit $q_j$ in $v_i$ is $1$ if $x_i$ appears in clause $j$; otherwise $q_j=0$

For example:

$\Psi=(x_1\lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor x_3)$

Let's try to prove correctness of the reduction.

Direction 1: Say subset sum has a solution $S'$.

We must prove that there is a satisfying assignment for $\Psi$.

Set $x_i=1$ if $v_i\in S'$

Set $x_i=0$ if $\overline{v_i}\in S'$

1. We want set $x_i$ to be both true and false, we will pick (in $S'$) either $v_i$ or $\overline{v_i}$
2. For each clause we have at least one literal that is true since $q_j$ has a $1$ in the clause.

Direction 2: Say $\Psi$ has a satisfying assignment.

We must prove that there is a subset $S'$ such that $\sum_{a_i\in S'} a_i = t$.

If $x_i=1$, then $v_i\in S'$

If $x_i=0$, then $\overline{v_i}\in S'$

Problem: 1,2 or 3 literals in every clause can be true.

Fix

Add 2 numbers to $S$ for each clause $j$. We add $y_j,z_j$.

• All $p$ digits are zero
• $q_j$ of $y_j$ is $1$, $q_j$ of $z_j$ is $2$, for all $j$, other digits are zero.
• Intuitively, these numbers account for the number of literals in clause $j$ that are true.

New target are as follows:

Time Complexity of construction for Subset Sum

• $O(n+m)$
• $n$ is the number of variables
• $m$ is the number of clauses

How many integers are in $S$?

• $2n$ for variables
• $2m$ for new numbers
• Total: $2n+2m$ integers

How many digits are in each integer?

• $n+m$ digits
• Time complexity: $O((n+m)^2)$

Proof of reduction for Subset Sum

Claim 1: If Subset Sum has a solution, then $\Psi$ is satisfiable.

Proof:

Say $S'$ is a solution to Subset Sum. Then there exists a subset $S' \subseteq S$ such that $\sum_{a_i\in S'} a_i = t$. Here is an assignment of truth values to variables in $\Psi$ that satisfies $\Psi$:

• Set $x_i=1$ if $v_i\in S'$
• Set $x_i=0$ if $\overline{v_i}\in S'$

This is a valid assignment since:

• We pick either $v_i$ or $\overline{v_i}$
• For each clause, at least one literal is true

EOP

Claim 2: If $\Psi$ is satisfiable, then Subset Sum has a solution.

Proof:

If $A$ is a satisfiable assignment for $\Psi$, then we can construct a subset $S'$ of $S$ such that $\sum_{a_i\in S'} a_i = t$.

If $x_i=1$, then $v_i\in S'$

If $x_i=0$, then $\overline{v_i}\in S'$

Say $t=\sum$ elements we picked from $S$.

• All $p_i$ in $t$ are $1$
• All $q_j$ in $t$ are either $1$ or $2$ or $3$.
  • If $q_j=1$, then $y_j,z_j\in S'$
  • If $q_j=2$, then $z_j\in S'$
  • If $q_j=3$, then $y_j\in S'$

EOP

Example 2: 3 Color

Input: Graph $G$

Problem: Determine if $G$ is 3-colorable.

We claim that 3-Color is NP-Complete.

Proof of NP for 3-Color

Homework

Proof of NP-Hard for 3-Color

We claim that 3-SAT $\leq_p$ 3-Color

Given a 3-CNF formula $\Psi$, we will construct a graph $G$ such that $\Psi$ is satisfiable if and only if $G$ is 3-colorable.

Construction:

1. Construct a core triangle (3 vertices for 3 colors)
2. 2 vertices for each variable $x_i:v_i,\overline{v_i}$
3. Clause widget

Clause widget:

• 3 vertices for each clause $C_j:y_j,z_j,t_j$ (clause widget)
• 3 edges extended from clause widget
• variable vertex connected to extended edges

Key for dangler design:

Connect to all $v_i$ with true to the same color. and connect to all $v_i$ with false to

// TODO: fix the picture put picture in public folder

Proof of reduction for 3-Color

Direction 1: If $\Psi$ is satisfiable, then $G$ is 3-colorable.

Proof:

Say $\Psi$ is satisfiable. Then $v_i$ and $\overline{v_i}$ are in different colors.

For the color in central triangle, we can pick any color.

For each dangler color is connected to blue, all literals cannot be blue.

...

EOP

Direction 2: If $G$ is 3-colorable, then $\Psi$ is satisfiable.

Proof:

EOP

Example 3:Hamiltonian cycle problem (HAMCYCLE)

Input: $G(V,E)$

Output: Does $G$ have a Hamiltonian cycle? (A cycle that visits each vertex exactly once.)

Proof is too hard.

but it is an existing NP-complete problem.

On lecture

Example 4: Scheduling problem (SCHED)

scheduling with release time, deadline and execution times.

Given $n$ jobs, where job $i$ has release time $r_i$, deadline $d_i$, and execution time $t_i$.

Example:

$S=\{2,3,7,5,4\}$. we created 5 jobs release time is 0, deadline is 26, execution time is $1$.

Problem: Can you schedule these jobs so that each job starts after its release time and finishes before its deadline, and executed for $t_i$ time units?

Proof of NP-completeness

Step 1: Show that the problem is in NP.

Certificate: $\langle (h_i,j_i),(h_2,j_2),\cdots,(h_n,j_n)\rangle$, where $h_i$ is the start time of job $i$ and $j_i$ is the machine that job $i$ is assigned to.

Verifier: Check that $h_i + t_i \leq d_i$ for all $i$.

Step 2: Show that the problem is NP-hard.

We proceed by proving that $SSS\leq_p$ Scheduling.

Consider an instance of SSS: $\{ a_1,a_2,\cdots,a_n\}$ and sum $b$. We can create a scheduling instance with release time 0, deadline $b$, and execution time $1$.

Then we prove that the scheduling instance is a "yes" instance if and only if the SSS instance is a "yes" instance.

Idea of proof:

If there is a subset of $\{a_1,a_2,\cdots,a_n\}$ that sums to $b$, then we can schedule the jobs in that order on one machine.

If there is a schedule where all jobs are finished by time $b$, then the sum of the scheduled jobs is exactly $b$.

Example 5: Component grouping problem (CG)

Given an undirected graph which is not necessarily connected. (A component is a subgraph that is connected.)

Problem: Component Grouping: Give a graph $G$ that is not connected, and a positive integer $k$, is there a subset of its components that sums up to $k$?

Denoted as $CG(G,k)$.

Proof of NP-completeness for Component Grouping

Step 1: Show that the problem is in NP.

Certificate: $\langle S\rangle$, where $S$ is the subset of components that sums up to $k$.

Verifier: Check that the sum of the sizes of the components in $S$ is $k$. This can be done in polynomial time using breadth-first search.

Step 2: Show that the problem is NP-hard.

We proceed by proving that $SSS\leq_p CG$. (Subset Sum $\leq_p$ Component Grouping)

Consider an instance of SSS: $\langle a_1,a_2,\cdots,a_n,b\rangle$.

We construct an instance of CG as follows:

For each $a_i\in S$, we create a chain of $a_i$ vertices.

WARNING: this is not a valid proof for NP hardness since the reduction is not polynomial for $n$, where $n$ is the number of vertices in the SSS instance.