Complexity NP-Complete Problems
2021-03-17 CSC373 Winter 2021 – Sam Toueg 1
Some NP-Complete Problems and
Reduction Techniques
2021-03-17 CSC373 Winter 2021 – Sam Toueg 2
Independent Set
2021-03-17 CSC373 Winter 2021 – Sam Toueg 5
Independent Set
• Undirected graph ! = ($, &)
Independent Set of size 3
• Independent Set (IS): Subset of nodes of ! that have no edges between them
2021-03-17 CSC373 Winter 2021 – Sam Toueg 6
Independent Set versus Clique
Clique of size 3 Independent Set of size 3
! = ( $ , & ) ! ̅ = $ , &(
&( = { ( * , + ) | * , + ∉ & }
( is a clique of ! ⇔ ( is an independent set of !̅ 2021-03-17 CSC373 Winter 2021 – Sam Toueg 7
Independent Set versus Clique
Claim: (isaCliqueof!=($,&)⇔(isanISof!̅= $,&+
Proof:
! is a clique of ” ⇔Forevery$and%in!, $,% ∈( ⇔Forevery$and%in!, $,%̅ ∉(* ⇔ ! is an Independent Set of ”
Corollary:!hasacliqueofsize,⇔ !̅hasanISofsize, 2021-03-17 CSC373 Winter 2021 – Sam Toueg 8
Independent Set Problem
• Input: Undirected graph ! = ($, &), integer ,
• Question: Does ! have an IS of size ,? • Claim: Independent Set is NP-Complete
2021-03-17 CSC373 Winter 2021 – Sam Toueg 10
Independence Set Problem
Claim: Independence Set is NP-Complete
• Independence Set is in NP
Ø Given any alleged independence set ! of , nodes of “,
it is easy to verify whether ! is indeed an IS of size , of ” • Clique ≤! Independent Set
ØSince “=(/,()hasaclique!ofsize,ifandonlyif “̅ = /, (* has an independent set ! of size ,
Ø Can transform̅ any instance (“, ,) of the Clique problem into an instance (“, ,) of the IS problem with the same answer
Ø This transformation takes polynomial time in the input size 2021-03-17 CSC373 Winter 2021 – Sam Toueg 11
Vertex Cover
2021-03-17 CSC373 Winter 2021 – Sam Toueg 16
Vertex Cover
• Undirected graph ! = ($, &)
vertex cover of size 2
• Vertex Cover (VC): Subset ( of nodes of ! that “covers’’ every edge !
i.e., every edge of ” is incident to at least one node in ! 2021-03-17 CSC373 Winter 2021 – Sam Toueg 17
Vertex Cover versus Independent Set • Undirected graph ! = ($, &)
vertex cover of size 2
independent set of size 3
•Claim: (isaVCof!⇒(̅=$−(isanISof! 2021-03-17 CSC373 Winter 2021 – Sam Toueg 18
Vertex Cover versus Independent Set • Undirected graph ! = ($, &)
vertex cover of size 2
independent set of size 3
̅̅
•ClaiSmo: (isanISof!⇒⇔(=$−(iisaVCoff!
2021-03-17 CSC373 Winter 2021 – Sam Toueg 19
Vertex Cover versus Independent Set •Claim: (isanISof!⇔(̅=$−(isaVCof!
• Proof:
! is an Independent Set of ”
⇔Forevery $,% ∈(,atmostoneof{$,%}isin! ⇔Forevery $,% ∈(,atleastoneof{$,%}isin!̅=/−! ⇔ !̅ = / − ! is a Vertex Cover of ”
2021-03-17 CSC373 Winter 2021 – Sam Toueg 20
Vertex Cover Problem
• Input: Undirected graph ! = ($, &), integer ,
• Question: Does ! have a Vertex Cover (VC) of size ,? Claim: Vertex Cover is NP-Complete
• Vertex Cover is in NP
Ø Given any alleged vertex cover ! of , nodes of “,
it is easy to verify whether ! is indeed a VC of size , of ” • Independent Set ≤! Vertex Cover
Ø Since: ” has an independent set ! of size , if and only if ” has a vertex cover !̅ = / − ! of size E − ,
Ø Can transform any instance (“, ,) of the IS problem into an instance (“, E − ,) of the VC problem with the same answer
2021-03-17 CSC373 Winter 2021 – Sam Toueg 22
Set Cover
2021-03-17 CSC373 Winter 2021 – Sam Toueg 25
Set Cover Problem
• Input:
Ø A universe of elements F,
Ø a family ! of subsets of F, and Ø an integer ,
• Question: Do there exist , sets from ! whose union is F? Example:
Ø F = {1,2,3,4,5,6,7}
Ø!= 1,3,7, 2,4,6, 4,5, 1, 1,2,6
Ø,=3
Are there 3 sets from # whose union is $? Yes! 1,3,7 , 4,5 ,{1,2,6}
Ø,=2
No!
2021-03-17 CSC373 Winter 2021 – Sam Toueg 26
Set Cover Problem
Claim: Set Cover is NP-Complete
• Set Cover is in NP
Ø Given any alleged set cover consisting of , sets of !,
it is easy to verify whether the union of these , sets is F • Vertex Cover ≤! Set Cover
ØGiven any ” = (/,() and ,
Ø Construct this instance of the set cover problem:
o Set $ = 0 (all the edges of 1 must be “covered’’)
o Set # = {#! | for all 3 ∈ 5, where #!: set of all the edges incident on 3} o Clearly:
• 1hasavertexcoverofsize7ifandonlyif • thereare7setsin#whoseunionis$
2021-03-17 CSC373 Winter 2021 – Sam Toueg 27
Reducing Vertex Cover to Set Cover Given: an instance (1, 7) of the Vertex Cover problem
2 13
1
5 vertex cover of size 0=2? YES!
4 5&4
2
3
VC = {2,4}
SC = {7″ = {1,2,5},7$ = {3,2,4,&}}
Construct the following instance of the Set Cover problem:
• 6 = {1,2,5,3,&,4},
• 7 = {7!, 7″, 7#, 7$, 7%} where
o 7! ={1,4},7″ ={1,2,5},7# ={5,3},7$ ={3,2,4,&},7% ={&} • 0=2
Clearly:
• !hasavertexcoverofsize2ifandonlyifthereare2setsin7whoseunionis6
2021-03-17 CSC373 Winter 2021 – Sam Toueg 28
Integer Programming Feasibility
2021-03-17 CSC373 Winter 2021 – Sam Toueg 34
IP Feasibility
• Problem
ØInput:N ∈ Q:,P ∈ Q:×< ØQuestion:DoesthereexistQ∈ 0,1
o:” =>?@#0and:̅” =;<$0iff:" =0and(1−:")=1
Ø For each clause Y of T:
o we want at least one of the three literals of B to be ;<$0
o so we require that their sum is at least 1 oE.g.,ifB=:#∨:̅$∨:̅%require:#+ 1−:$ + 1−:% ≥1
Ø Easy to check that
o this is a polynomial reduction
o Resulting system has a feasible solution iff F is satisfiable
2021-03-17 CSC373 Winter 2021 - Sam Toueg 38
Graph Coloring
2021-03-17 CSC373 Winter 2021 - Sam Toueg 39
Coloring
• Problem
Ø Input: Undirected graph " = (/, (), integer ,
Ø Question: Can we color each node of " using at most , colors such that no two adjacent nodes have the same color?
Example:
Can we color this graph
only 0 = 3 colors?
Claim: Coloring is NP-Complete
2021-03-17 CSC373 Winter 2021 - Sam Toueg 40
Coloring
• Claim: Coloring is in NP
Because:
Ø given any alleged ,-coloring of a graph "
Ø it is easy to verify that it is indeed a correct ,-coloring of ":
check that no edge of " has end-points with the same color Ø This can be done in time polynomial in the size of ", ,
2021-03-17 CSC373 Winter 2021 - Sam Toueg 41
Coloring
• Claim: 3SAT ≤! Coloring Because:
Ø Given any 3CNF formula T, we can construct a graph " and and a , (i.e., we can construct an instance (", ,) of Coloring) such that: T is satisfiable iff " is ,-colorable
2021-03-17 CSC373 Winter 2021 - Sam Toueg 42
Given any CNF formula A with 0 variables, can construct a graph ! such that: ! is (0 + 1)-colorable ⇐⇒ A is satisfiable
Example: this A has 0 = 3 variables A= >!∨>̅”∨>̅# ∧ >̅!∨>”∨>̅#
! is 4-colorable >! ∨>̅” ∨>̅#
T
> ! T TF
+! TT
> ̅ ! TF F
>”TF +”
5!
4
A is satisfiable
> ̅ ” TF
5″ >̅! ∨>” ∨>̅#
># TF +#
>̅# TF
T
a 4-coloring of ! ⇒ a truth assignment to Boolean variables
2021-03-17 CSC373 Winter 2021 – Sam Toueg 43
Given any CNF formula A with 0 variables, can construct a graph ! such that: ! is (0 + 1)-colorable ⇐⇒ A is satisfiable
>!
Example: this A has 0 = 3 variables A= >!∨>̅”∨>̅# ∧ >̅!∨>”∨>̅#
+! FTFTFF
>̅!
>”
>̅”
5!
! is 4-colorable >! ∨>̅” ∨>̅#
T
4
+”
A is satisfiable
with truth assignment:
5″
>!= F, >” = F, ># = T >̅! ∨>” ∨>̅#
># +#
>̅#
T
a 4-coloring of ! ⇒ a truth assignment to Boolean variables 2021-03-17 CSC373 Winter 2021 – Sam Toueg
46