NP-Completeness (2)

Vertex Cover Problem

Vertex Cover Problem

• A vertex cover of an undirected graph $G=(V,E)$ is a subset $V' \sube V$ such that if $(u,v) \in E$, then $u\in V'$ or $v \in V'$ (or both)
  Graph 의 어떤 Edge 이든 edge를 이루는 두 vertex 중 하나는 $V'$ 에 속함
• The size of a vertex cover is the number of vertices in it
  • A vertex cover $\{w,z\}$ of size 2
    

Goal: Finding a vertex cover of minimum size in a given graph

Optimization problem $\rightarrow$ Decision problem

• Input: An undirected graph $G=(V,E)$ and an integer $k$
• Question: Is there a vertex cover of a given size $k$?

---

Vertex Cover Problem (NPC Proof)

1. NP 인지 증명 (=Polynomial time 으로 verification 가능해야함)

• $k$ 개의 edge 집합 $V'$ 가 주어진다면, edge 가 다 존재하는지 확인
  $\rightarrow$ Polynomial time 으로 확인 가능

2. NP Complete Problem 으로부터 Polynomial time 으로 reduction 가능해야함

• Clique $\leq_p$ Vertex Cover
  • Complement of $G=(V,E)$ is $\bar{G}=(V,\bar{E})$ where
    $\bar{E}=\{(u,v):u,v \in V, u\neq v$ and $(u,v) \notin E\}$
• Reduction algorithm
  • Input: $<G,k>$ of the clique problem
  • Compute $\bar{G}$ in polynomial time
  • Output: $<\bar{G},|V|-k>$
    
• The graph $G$ has a clique of size $k$ iff the graph $\bar{G}$ has a vertex cover of size $|V|-k$
  • Clique $\rightarrow$ Vertex Cover
  • Suppose that $G$ has a clique $V' \sube V$ with $|V'|=k$
  • For any edge $\in \bar{E}$
    • At least one of $u$ or $v$ does not belong to $V'$
    • Equivalently, at least one of $u$ or $v$ is in $V-V'$ $\rightarrow$ edge $(u,v)$ is covered by $V-V'$
  • Every edge of $\bar{E}$ is covered by $V-V'$
  • $\bar{G}$ 에 존재하는 edge 의 두 vertex 중 적어도 하나는 반드시 clique 에 속하지 않은 vertex 이다.
  • Vertex Cover $\rightarrow$ Clique
  • Suppose that $\bar{G}$ has a vertex cover $V' \sube V, |V'|=|V|-k$
  • For all $u,v \in V$, if $(u,v)\in \bar{E}, u \in V' \text{ or } v \in V'$
  • The contrapositive of this implication is
    • For all $u,v \in V$, if $u \notin V'$ and $v \notin V'$, then $(u,v) \in E$
    • $\Rightarrow$ $V-V'$ has a clique with size $|V-V'|=k$

---

Subgraph Isomorphism

Subgraph Isomorphism

• Isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$
  • $f:V(G) \rightarrow V(H)$
  • Any two vertices $u$ and $v$ of $G$ are adjacent in $G$ iff $f(u)$ and $f(v)$ are adjacent in $H$
    

---

Subgraph Isomorphism Problem

• Input: $G_1=(V_1, E_1),G_2=(V_2, E_2)$
• Question: Does $G=(V, E)$ with $V \sube V_1$, $E \sube E_1$ exist such that $|V|=|V_2|, |E|=|E_2|$ and
  there is a one to one function $f:V\rightarrow V_2$ satisfying $\{u,v\} \in E$ if $\{f(u), f(v)\} \in E_2$?
  $G_1$ 의 subgraph $G$ 가 $G_2$ 와 isomorphism 인지 찾는 문제

---

Subgraph Isomorphism Problem (NPC Proof)

1. NP 증명 (=Polynomial time 으로 verification 가능해야함)

• Given $G_1=(V_1, E_1), G_2=(V_2, E_2)$, for $G=(V,E)$ and $f$,
  we can verify that $G$ is subgraph of $G_1$ and isomorphic to $G_2$ in polynomial time
  • By checking
  • $V \sube V_1, E \sube E_1$, $|V|=|V_2|, |E|=|E_2|$
  • Every $\{u,v\} \in E_2$ satisfy $\{f(u),f(v)\} \in E$

2. NP Complete Problem 으로부터 Polynomial time 으로 reduction 가능해야함

• Clique $\leq_p$ Subgraph Isomorphism
• Reduction algorithm
  • Input: $<G,k>$ of the clique problem
  • Generate a complete graph $G_2$ of size $k$ in polynomial time
  • Output: $<G_1, G_2>$
    
• Clique $\rightarrow$ Subgraph Isomorphism
  • $G_1$이 $k$-clique 을 가진다면 생성된 $G_2$ 와 isomorphic한 $G \sube G_1$ 가 존재
  • $G_1$이 $k$-clique 을 가지지 않는다면 생성된 $G_2$ 에 대해 어떤 $f$도 isomorphism 만족 불가
• Subgraph Isomorphism $\rightarrow$ Clique
  • $G \sube G_1$ 가$G_2$와 isomorphic 하다면 $G_1$이 $k$-clique 을 가짐

---

Hitting Set

Hitting Set

• Given a set $T$ and a collection of sets $C=\{S_1, S_2,\dots,S_n\}$ where each $S_i$ is a subset of $T$
• A hitting set $H$ is a subset of $T$ which intersects all sets in the collection with at least one element
  • for all $i \in \{1,2,\dots,n\}$, we have $H \cap S_i \neq \cancel{0}$
  • e.g.
    • $T=\{1,2,3,4,5\}$
    • $C=\{\{1,2\},\{1,3\},\{3,4,5\}\}$
    • $H=\{1,3\}$

---

Hitting Set Problem

• Finding a hitting set $H$ of $T$ with the minimum size

Optimization problem $\rightarrow$ Decision problem

• Input: A set $T$, a collection of sets $C=\{S_1,S_2,\dots,S_n\}$, where each $S_i$ is a subset of $T$ and integer $k$
• Question: Is there a hitting set $H$ of $T$ with $|H|=k$?

---

Hitting Set Problem (NPC Proof)

1. NP 증명 (=Polynomial time 으로 verification 가능해야함)

• For the certificate of a hitting set $H$, affirms that $|H|=k$
• Check $H \cap S_i \neq 0$ for $i=1,\dots,n$

2. NP Complete Problem 으로부터 Polynomial time 으로 reduction 가능해야함

• Vertex Cover $\leq_p$ Hitting Set
  • Let $<G,k>$ be an instance of the vertex cover problem and $G=(V,E)$
  • Let $T=V$ and for all $(u,v) \in E$, add a new set $\{u,v\}$ to the collection $C$
    • 여기서 $S_i$ 사이즈는 2개인 것만
  • Show that there is a hitting set $H$ of size $k$ iff if $G$ has a vertex cover $C$ of size $k$
• Vertex Cover $\rightarrow$ Hitting Set
  • Suppose there is a vertex $C$ for $G$ for size $k$
    For each edge $(u,v)$ either $u \in C$ or $v \in C$
    Setting $C$ to be $H$ gives a hitting set of size $k$
• Hitting Set $\rightarrow$ Vertex Cover
  • Suppose there is a hitting set $H$ of size $k$
    Since $H$ contains at least one endpoint of each edge,
    setting $C$ to be $H$ gives a vertex cover of size $k$

---

Subset-Sum

Subset-Sum Problem

• Input: A finite set $S$ of positive integers and an integer target $t > 0$
• Question: Is there a subset $S' \sube S$ whose elements sum to $t$?
• e.g.
  • $S=\{1,2,7,14,49,98,343,686,2409,2793\}$ and $t=451$
  • $S'=\{1,2,7,98,343\}$

---

Subset-Sum (NPC Proof)

1. Subset-Sum $\in$ NP

• For an instance $<S,t>$, let the subset $S'$ be the certificate
• Checking whether $t=\displaystyle\sum_{s\in S'}s$ can be verified in polynomial time

2. 3-CNF-SAT $\leq_p$ Subset-Sum

• Given 3-CNF formula $\phi$ over variable $x_1,x_2,\dots,x_n$ with clauses $C_1,C_2,\dots,C_k$
• Assumption without loss of generality
• Reduction algorithm
  • Input:
    • $\phi = C_1 \land C_2 \land C_3 \land C_4$
    • $C_1=(x_1 \lor \lnot x_2 \lor \lnot x_3)$
    • $C_2=(\lnot x_1 \lor \lnot x_2 \lor \lnot x_3)$
    • $C_3=(\lnot x_1 \lor \lnot x_2 \lor x_3)$
    • $C_4=(x_1 \lor x_2 \lor x_3)$
  • Label each digit position
    • variable: the most significant $n$ digits
    • clause: the least signifiacant $k$ digits
  • $v_i$ and $v_i'$
    • $x_i$ set to 1 if $i$ is same as $v_i$
    • $C_i$ set to 1 depending on variables in the clause
  • $s_j$ and $s_j'$
    • For each clause $C_j$,
      For $s_j$, there is a 1 in the $C_j$ digit and $s_j'$ has a 2 in this digit (=slack variables)
      the ohter $s_j$ has 0
      
  • Output:
    • $S=\{1001001, 1000110, \cdots, 1000, \cdots, 2\}$
      Each row becomes $S_i$
    • $t=1114444$
      A 1 in each variable-labeled digit and a 4 in each clause-labeled digit
  • 모든 $i$ 에 대하여 $v_i$ 와 $v_i'$ 중 반드시 하나씩 선택
  • $C_i$ 는 1개 이상만 선택되면 됨
• 3-CNF-SAT $\rightarrow$ Subset-Sum
  • Suppose that $\phi$ has a satisfying assignment
    $<x_1=0, x_2=0, x_3=1>$
  • If $x_i=1$, then include $v_i$ in $S'$
  • If $x_i=0$, then include $v_i'$ in $S'$
  • $S'$ includes $\{v_1', v_2', v_3\}$
  • True 가 되는 assignment 를 가진다면,
    $C_i$ 중 $v_i,v_i'$ 는 둘 중 하나만 선택되어 $t$ 의 $x_i$ digit,
    $s_i,s_i'$ 를 통해 $t$ 의 $C_i$ digit 을 만족 가능
• Subset-Sum $\rightarrow$ 3-CNF-SAT
  • Suppose that there is a subset $S' \sube S$ that sums to $t$
  • If $v_i\in S'$, set $x_i=1$
  • If $v_i'\in S'$, set $x_i=0$
  • Every clause $C_j$, for $j=1,\dots, k$ is satisfied by this assignment
    
• By the subset $S'$ (yellow) matches to the $t$, every $C_j$ set to 1

---

Partition

Partition Problem

• Input: A finite set $S$ of numbers
• Question: Can the numbers in $S$ be partitioned into two sets $S_1$ and $S_2=S-S_1$ such that Summation of $S_1$ and $S_2$ are equal
• e.g.
  • $S=\{1,2,7,10\}$
  • $S_1=\{1,2,7\},S_2=\{10\}$

---

Partition Problem (NPC Proof)

1. Partition $\in$ NP

• For a set $S$, let the subsets $S_1$ and $S_2=S-S_1$ be the certificate
• Checking whether summation can be accomplished by a verficiation in polynomial time

2. Subset-Sum $\leq_p$ Partition

• Reduction algorithm
  • Input: $<S,t>$ of the subset-sum problem
  • $S'=S \cup \{2a,3a,4a+2t\}, a=(\Sigma_{x \in S}x)$
  • Output: $<S'>(\Sigma_{x \in S},x=10a+2t)$

• If there is $B'$ that $\Sigma_{x\in B'}x=t$, make $C'=B' \cup \{2a,3a\}$
  • $\Sigma_{x\in C'}x=t + 2a+3a=5a+t$
  • $\Sigma_{x\in (S'-C')}x=10a+2t-\Sigma_{x \in C'}x=5a+t$
  • Therefore, partition exists
• Subset-Sum $\rightarrow$ Partition
  • 만약 합이 $t$ 인 set $A \sube S$ 가 존재한다면 $A \cup \{2a,3a\}$ 로 partiton 가능
• Partition $\rightarrow$ Subset-Sum
  • $4a+2t$ 는 $2a, 3a$ 와 같은 집합이 될 수 없음
  • $4a+2t$ 와 같이 partition 되는 집합의 합은 $a-t$
    반대 set 은 $2a+3a=5a$ $\rightarrow$ 나머지 부분집합의 합이 $t$ 이어야함
  • 따라서 $S'$ 의 원소 중에서 합이 $t$인 부분집합이 존재

---