Set cover Intractability: quiz 4
SET-COVER. Given a set U of elements, a collection S of subsets of U, and an Given the universe U = { 1, 2, 3, 4, 5, 6, 7 } and the following sets,
integer k, are there ≤ k of these subsets whose union is equal to U ? which is the minimum size of a set cover?
Sample application.
A. 1 U = { 1, 2, 3, 4, 5, 6, 7 }
・m available pieces of software.
・Set U of n capabilities that we would like our system to have. B. 2 Sa = { 1, 4, 6 } Sb = { 1, 6, 7 }
・The ith piece of software provides the set Si ⊆ U of capabilities. C. 3 Sc = { 1, 2, 3, 6 } Sd = { 1, 3, 5, 7 }
・Goal: achieve all n capabilities using fewest pieces of software. D. None of the above.
Se = { 2, 6, 7 } Sf = { 3, 4, 5 }
U = { 1, 2, 3, 4, 5, 6, 7 }
Sa = { 3, 7 } Sb = { 2, 4 }
Sc = { 3, 4, 5, 6 } Sd = { 5 }
Se = { 1 } Sf = { 1, 2, 6, 7 }
k=2
a set cover instance
19 20
Vertex cover reduces to set cover Vertex cover reduces to set cover
Theorem. VERTEX-COVER ≤ P SET-COVER. Lemma. G = (V, E) contains a vertex cover of size k iff (U, S, k) contains
Pf. Given a VERTEX-COVER instance G = (V, E) and k, we construct a a set cover of size k.
SET-COVER instance (U, S, k) that has a set cover of size k iff G has a
vertex cover of size k. Pf. ⇒ Let X ⊆ V be a vertex cover of size k in G. “yes” instances of VERTEX-COVER
・Then Y = { Sv : v ∈ X } is a set cover of size k. ▪
are solved correctly
Construction.
・Universe U = E.
・Include one subset for each node v ∈ V : Sv = {e ∈ E : e incident to v }.
a b a b
e7 e2 e4 U = { 1, 2, 3, 4, 5, 6, 7 } e7 e2 e4 U = { 1, 2, 3, 4, 5, 6, 7 }
e3 e3
Sa = { 3, 7 } Sb = { 2, 4 } Sa = { 3, 7 } Sb = { 2, 4 }
f e6 c f e6 c
Sc = { 3, 4, 5, 6 } Sd = { 5 } Sc = { 3, 4, 5, 6 } Sd = { 5 }
e1 e5 Se = { 1 } Sf = { 1, 2, 6, 7 } e1 e5 Se = { 1 } Sf = { 1, 2, 6, 7 }
e d e d
vertex cover instance set cover instance vertex cover instance set cover instance
(k = 2) (k = 2) (k = 2) (k = 2)
21 22
Vertex cover reduces to set cover
Lemma. G = (V, E) contains a vertex cover of size k iff (U, S, k) contains
a set cover of size k. 8. I NTRACTABILITY I
Pf. ⇐ Let Y ⊆ S be a set cover of size k in (U, S, k). “no” instances of VERTEX-COVER ‣ poly-time reductions
・Then X = { v : Sv ∈ Y } is a vertex cover of size k in G.
are solved correctly
▪
‣ packing and covering problems
‣ constraint satisfaction problems
‣ sequencing problems
‣ partitioning problems
a b
‣ graph coloring
e7 e2 e4 U = { 1, 2, 3, 4, 5, 6, 7 }
e3
Sa = { 3, 7 } Sb = { 2, 4 } ‣ numerical problems
SECTION 8.2
f e6 c
Sc = { 3, 4, 5, 6 } Sd = { 5 }
e1 e5 Se = { 1 } Sf = { 1, 2, 6, 7 }
e d
vertex cover instance set cover instance
(k = 2) (k = 2)
23
Satisfiability Satisfiability is hard
Literal. A Boolean variable or its negation. xi or xi Scientific hypothesis. There does not exist a poly-time algorithm for 3-SAT.
Clause. A disjunction of literals. C j = x1 ∨ x2 ∨ x3 P vs. NP. This hypothesis is equivalent to P ≠ NP conjecture.
€
Conjunctive normal form (CNF). A propositional Φ = C1 ∧ C2 ∧ C3 ∧ C4
formula Φ that is a conjunction of clauses. €
SAT. Given a CNF formula Φ, does it have a satisfying
€ truth assignment?
3-SAT. SAT where each clause contains exactly 3 literals
(and each literal corresponds to a different variable).
Φ = ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 4 )
yes instance: x1 = true, x2 = true, x3 = false, x4 = false
€ https://www.facebook.com/pg/npcompleteteens
Key application. Electronic design automation (EDA).
25 26
3-satisfiability reduces to independent set 3-satisfiability reduces to independent set
Theorem. 3-SAT ≤ P INDEPENDENT-SET. Lemma. Φ is satisfiable iff G contains an independent set of size k = ⎜Φ ⎜.
Pf. Given an instance Φ of 3-SAT, we construct an instance (G, k) of
INDEPENDENT-SET that has an independent set of size k = ⎜Φ ⎜ iff Φ is satisfiable. Pf. ⇒ Consider any satisfying assignment for Φ.
・Select one true literal from each clause/triangle. “yes” instances of 3-SAT
are solved correctly
Construction. ・This is an independent set of size k = ⎜Φ ⎜. ▪
・G contains 3 nodes for each clause, one for each literal.
・Connect 3 literals in a clause in a triangle.
・Connect literal to each of its negations.
G G
k=3 k=3
Φ = ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 4 ) Φ = ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 4 )
27 28
€ €
3-satisfiability reduces to independent set Review
Lemma. Φ is satisfiable iff G contains an independent set of size k = ⎜Φ ⎜. Basic reduction strategies.
・Simple equivalence: INDEPENDENT-SET ≡ P VERTEX-COVER.
Pf. ⇐ Let S be independent set of size k. ・Special case to general case: VERTEX-COVER ≤ P SET-COVER.
・S must contain exactly one node in each triangle. “no” instances of 3-SAT
are solved correctly ・Encoding with gadgets: 3-SAT ≤ P INDEPENDENT-SET.
・Set these literals to true (and remaining literals consistently).
・All clauses in Φ are satisfied. ▪
Transitivity. If X ≤ P Y and Y ≤ P Z, then X ≤ P Z.
Pf idea. Compose the two algorithms.
Ex. 3-SAT ≤ P INDEPENDENT-SET ≤ P VERTEX-COVER ≤ P SET-COVER.
k=3
Φ = ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 4 )
29 30
