CSE347 Analysis of Algorithms (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$

Ideas 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.

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

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 another color.

Proof of reduction for 3-Color

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

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

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.

Ideas 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.