Complexity NP-Complete Problems
2021-03-22 CSC373 Winter 2021 – Sam Toueg 1
Some NP-Complete Problems and
Reduction Techniques
2021-03-22 CSC373 Winter 2021 – Sam Toueg 48
Last week…
• Defined P and NP
• Defined NP-Hard and NP-Complete
• Some NP-Complete Problems: ØSAT
Ø Clique
Ø Independent Set Ø Vertex Cover
Ø Set Cover
Ø IP Feasibility
Ø Coloring
[SAT ≤F Clique]
[Clique ≤F Independent Set] [Independent Set ≤F Vertex Cover] [Vertex Cover ≤F Set Cover]
[3SAT ≤F IP Feasibility]
[3SAT ≤F Coloring]
2021-03-22
CSC373 Winter 2021 – Sam Toueg 49
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?
Theorem: Coloring is NP-Complete
2021-03-22 CSC373 Winter 2021 – Sam Toueg 50
Exact Set Cover
2021-03-22 CSC373 Winter 2021 – Sam Toueg 51
Exact Set Cover Problem
• Input:
Ø A universe of elements F, Ø a family ! of subsets of F
• Question: Are there disjoint sets in ! whose union is F? Example:
Ø F = {1,2,3,4,5,6,7,8}
Ø!= 1,3,7,8, 2,4,6, 4,5, 1, 3,5, 1,7,8 Ø Are there disjoint sets in # whose union is $?
Yes! 2,4,6 , 3,5 ,{1,7,8}
2021-03-22
CSC373 Winter 2021 – Sam Toueg 52
Exact Set Cover Problem
Claim: Exact Set Cover is NP-Complete
• Exact Set Cover is in NP
Ø Given any alleged exact set cover of F,
it is easy to verify whether:
o the sets in the set cover are disjoint
o their union is $
• Coloring ≤! Exact Set Cover
Ø Given any instance ” = (/, () and , of the Coloring problem
Ø Build an instance (F, !) of the exact set cover problem such that:
o 1 can be colored with 7 colors if and only if
o There is an exact set cover: ∃ disjoint sets in # whose union is $
Ø How do we do this?
2021-03-22 CSC373 Winter 2021 – Sam Toueg 53
Reducing Coloring to Exact Set Cover
Basic idea:
• transform a color conflict over a shared edge into a set intersection • How? By extending the color of a node to its incident edges
*I+ *I+
{ I,JKIIL }∩{ I,KIP }=∅ G = encoding of color green
H = encoding of color red {I,G}∩{I,H}=∅
With correct node coloring: set of colored edges by *
does not intersect
set of colored edges by +
{ I,JKIIL }∩{ I,JKIIL }≠∅
{I,G}∩{I,G }≠∅
With incorrect node coloring: set of colored edges by *
intersects
set of colored edges by +
2021-03-22
CSC373 Winter 2021 – Sam Toueg 54
Reducing Coloring to Exact Set Cover
Given a graph 1 = (5, 0) and an integer 7 [can we color 1 with 7 colors?] Construct the following instance of the Exact Set Cover problem:
• $=5∪{J,K |J∈0∧1≤K≤7}
• # = family of subsets of $ that contains:
Ø7&’ ={+}∪{I,G |I∈&GLVGPILWWX+}foreach+∈$andeachcolor1≤G≤0 ØZ(‘ ={I,G}foreachedgeI∈&andeachcolorG,1≤G≤0.
Example: ! = ($, &) and (=3
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]}
• 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3}
!!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
S
R
cd
Q 57
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
K
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U • *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]}
• 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3}
!!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 }
!&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
S
R
cd
Q 58
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
K
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3} !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 59
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3} !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 60
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#” ={+}∪{ .,2 , 1,2 } !#* ={+}∪{ .,3 , 1,3 } !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
!#$ ={+}∪{.,1,1,1}
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 61
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#” ={+}∪{ .,2 , 1,2 } !#* ={+}∪{ .,3 , 1,3 } !!” ={$}∪{‘,2} !!* ={$}∪{‘,3}
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
!#$ ={+}∪{.,1,1,1}
!!$ ={$}∪{‘,1}
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 62
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#” ={+}∪{ .,2 , 1,2 } !#* ={+}∪{ .,3 , 1,3 } !!” ={$}∪{‘,2} !!* ={$}∪{‘,3}
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
!#$ ={+}∪{.,1,1,1}
!!$ ={$}∪{‘,1}
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 63
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#” ={+}∪{ .,2 , 1,2 } !#* ={+}∪{ .,3 , 1,3 } !!” ={$}∪{‘,2} !!* ={$}∪{‘,3}
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 }
!#$ ={+}∪{.,1,1,1}
!!$ ={$}∪{‘,1}
!&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 64
!&* ={-}∪{1,3],[2,3}
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U ⇒
????
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#” ={+}∪{ .,2 , 1,2 } !#* ={+}∪{ .,3 , 1,3 } !!” ={$}∪{‘,2} !!* ={$}∪{‘,3}
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 }
!#$ ={+}∪{.,1,1,1}
!!$ ={$}∪{‘,1}
!&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3}
*
R
S
K 1 = green c d 2=red
3=blue Q 65
!&* ={-}∪{1,3],[2,3}
2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
We showed
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇒S has an exact cover of U
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3} !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
S
R
cd
Q 67
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
K
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
We now show
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇐S has an exact cover of U
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3} !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
S
R
cd
Q 68
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
K
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
• Suppose ! has an exact cover of *
• It must cover the elements +, $, ,, – that are in *, and do so without “repetitions’’
• So this exact cover of * must contain exactly one !#∗ , one !!∗, one !%∗ and one !&∗
• Say the exact cover contains !#” , !!* , !%$ , and !&*
• Colornode+with2,$with3,,with1,and-with3
• Since !#” , !!* , !%$ , and !&* are disjoint (because they are part of an exact cover!)
any two nodes in +, $, ,, – with the same color do not share an edge! ⇒ this is a correct coloring of 7
Claim: G is 3-colorable ⇔⇐ S has an exact cover of U
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2,
• 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* !!$ ={$}∪{‘,1} !!” ={$}∪{‘,2} !!*
={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{1,1,[2,1]} !&” ={-}∪{1,2],[2,2} !&* ={-}∪{1,3],[2,3}, 8,3}
‘,3, 2,1, 2,2,[2,3]}
={+}∪{.,3, 1,3} ={$}∪{‘,3}, 8,3}
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%*
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
R
S
K 1 = green c d 2=red
3 = blue Q 70
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
I
Reducing Coloring to Exact Set Cover
So we showed
Example: ! = ($, &) and (=3 Claim: G is 3-colorable ⇔ S has an exact cover of U
• *={+,$,,,-}∪{.,1, .,2, .,3, 1,1, 1,2, 1,3, ‘,1, ‘,2, ‘,3, 2,1, 2,2,[2,3]} • 7 = family of subsets of 6 that contains:
!#$ ={+}∪{.,1, 1,1} !#” ={+}∪{.,2, 1,2} !#* ={+}∪{.,3, 1,3} !!$ ={$}∪{ ‘,1 } !!” ={$}∪{ ‘,2 } !!* ={$}∪{ ‘,3 }
!%$ ={,}∪{ .,1 , ‘,1 ,[2,1]} !%” ={,}∪{ .,2 , ‘,2 ,[2,2]} !%* ={,}∪{ .,3 , ‘,3],[2,3 } !&$ ={-}∪{ 1,1 ,[2,1]} !&” ={-}∪{ 1,2],[2,2 } !&* ={-}∪{ 1,3],[2,3 }
5’$ ={.,1} 5($ ={1,1} 5)$ ={‘,1} 5+$ ={2,1}
S
R
cd
Q 75
* 5′” ={.,2} 5(” ={1,2} 5)” ={‘,2} 5+” ={2,2}
K
5’* ={.,3} 5(* ={1,3} 5)* ={‘,3} 5+* ={2,3} 2021-03-22 CSC373 Winter 2021 – Sam Toueg +
Reducing Coloring to Exact Set Cover
Claim: ! is “-colorable ⇐ $ has an exact cover of %
Proof:
• Since & ⊆ % , the exact cover of % must contain
exactly one $!∗ , namely $!#! for some color (! , for each node ) ∈ &
• Color each node ) with (!
• We claim that this is a correct coloring of !:
• Suppose, for contradiction, that two nodes , and ) that share the same edge – are colored with the same color ..
• Then ($ = (! = . and both $$% and $!% contain the element -,.
• So the exact cover contains two sets that are not disjoint — a contradiction!
2021-03-22 CSC373 Winter 2021 – Sam Toueg 76
Exact Set Cover Problem
Recap: We proved that Exact Set Cover is NP-Complete
• Exact Set Cover is in NP
Ø Easy to verify that any alleged exact set cover of F,
is indeed a correct one
• Coloring ≤! Exact Set Cover
Ø Given any instance ” = (/, () and , of the Coloring problem
Ø Built an instance (F, !) of the exact set cover problem s.t.: o 1 can be colored with 7 colors if and only if
o There are disjoint sets in # whose union is $
2021-03-22 CSC373 Winter 2021 – Sam Toueg 78
2021-0C3S-2C2373 Winter 2021 – Sam Toueg
98
CSC373 Winter 2020
3SAT
SAT
Subset sum
Vertex Cover
Clique
Partition
⋮⋮
2C0SC213-7033W-22inter 2021 – Sam Toueg
99