程序代写代做代考 algorithm graph C CSE 521: Design & Analysis of Algorithms I

CSE 521: Design & Analysis of Algorithms I
NP-completeness
Paul Beame
1

Computational Complexity
􏰄 Classify problems according to the amount of computational resources used by the best algorithms that solve them
􏰄 Recall:
􏰄 worst-case running time of an algorithm
􏰄 max # steps algorithm takes on any input of size n
2

Relative Complexity of Problems
􏰄 Want a notion that allows us to compare the complexity of problems
􏰄 Want to be able to make statements of the form
“If we could solve problem B in polynomial time then we can solve problem A in polynomial time”
“Problem B is at least as hard as problem A”
3

Polynomial Time Reduction
􏰄 A ≤P B if there is an algorithm for A using a ‘black box’ (subroutine) that solves B that
􏰄 Uses only a polynomial number of steps
􏰄 Makes only a polynomial number of calls to a subroutine for
B
􏰄 Thus, poly time algorithm for B implies poly time algorithm for A
􏰄 Not only is the number of calls polynomial but the size of the inputs on which the calls are made is polynomial!
􏰄 If you can prove there is no fast algorithm for A, then that proves there is no fast algorithm for B
4

Why the name reduction?
􏰄 Weird: it maps an easier problem into a harder one
􏰄 Same sense as saying Maxwell reduced the problem of analyzing electricity & magnetism to solving partial differential equations
􏰄 solving partial differential equations in general is a much harder problem than solving E&M problems
5

A geek joke
􏰄 An engineer
􏰄 is placed in a kitchen with an empty kettle on the table and told to boil water; she fills the kettle with water, puts it on the stove, turns on the gas and boils water.
􏰄 she is next confronted with a kettle full of water sitting on the counter and told to boil water; she puts it on the stove, turns on the gas and boils water.
􏰄 A mathematician
􏰄 is placed in a kitchen with an empty kettle on the table and told to boil water; he fills the kettle with water, puts it on the stove, turns on the gas and boils water.
􏰄 he is next confronted with a kettle full of water sitting on the counter and told to boil water: he empties the kettle in the sink, places the empty kettle on the table and says, “I’ve reduced this to an already solved problem”.
6

A Special kind of Polynomial-Time Reduction
􏰄 We will always use a restricted form of polynomial-time reduction often called Karp or many-one reduction
􏰄 A≤1 B if and only if there is an algorithm for A P
given a black box solving B that on input x
􏰄 Runs for polynomial time computing an input f(x) 􏰄 Makes one call to the black box for B
􏰄 Returns the answer that the black box gave
We say that the function f is the reduction
7

Reductions by Simple Equivalence
􏰄 Show: Independent-Set ≤P Clique 􏰄 Independent-Set:
􏰄 Given a graph G=(V,E) and an integer k, is there a subset U of V with |U| ≥ k such that no two vertices in U are joined by an edge?
􏰄 Clique:
􏰄 Given a graph G=(V,E) and an integer k, is there a subset U of V with |U| ≥ k such that every pair of vertices in U is joined by an edge?
8

Independent-Set ≤P Clique
􏰄 Given (G,k) as input to Independent-Set
where G=(V,E)
􏰄 Transform to (G’,k) where G’=(V,E’) has the same vertices as G but E’ consists of precisely those edges that are not edges of G
􏰄 U is an independent set in G ⇔ U is a clique in G’
9

More Reductions
􏰄 Show: Independent Set ≤P Vertex-Cover 􏰄 Vertex-Cover:
􏰄 Given an undirected graph G=(V,E) and an integer k is there a subset W of V of size ≤ k such that every edge of G has at least one endpoint in W? (i.e. W covers all edges of G)?
􏰄 Independent-Set:
􏰄 Given a graph G=(V,E) and an integer k, is there a subset U of V with |U| ≥ k such that no two vertices in U are joined by an edge?
10

Reduction Idea
􏰄 Claim: In a graph G=(V,E), S is an independent set iff V-S is a vertex cover
􏰄 Proof:
􏰄 ⇒ Let S be an independent set in G
􏰄 Then S contains at most one endpoint of each edge of G
􏰄 At least one endpoint must be in V-S
􏰄 V-S is a vertex cover
􏰄 ⇐Let W=V-S be a vertex cover of G
􏰄 Then S does not contain both endpoints of any edge (else W would miss that edge)
􏰄 S is an independent set
11

Reduction
􏰄 Map (G,k) to (G,n-k)
􏰄 Previous lemma proves correctness
􏰄 Clearly polynomial time
􏰄 We also get that
􏰄 Vertex-Cover ≤P Independent Set
12

Reductions from a Special Case to a General Case
􏰄 Show: Vertex-Cover ≤P Set-Cover 􏰄 Vertex-Cover:
􏰄 Given an undirected graph G=(V,E) and an integer k is there a subset W of V of size at most k such that every edge of G has at least one endpoint in W? (i.e. W covers all edges of G)?
􏰄 Set-Cover:
􏰄 Given a set U of n elements, a collection S1,…,Sm of subsets of U, and an integer k, does there exist a collection of at most k sets whose union is equal to U?
13

The Simple Reduction
􏰄 Transformation f maps (G=(V,E),k) to (U,S1,…,Sm,k’)
􏰄 U←E
􏰄 For each vertex v∈V create a set Sv
containing all edges that touch v 􏰄 k’←k
􏰄 Reduction f is clearly polynomial-time to compute
􏰄 We need to prove that the resulting algorithm gives the right answer.
14

Proof of Correctness
􏰄 Two directions:
􏰄 If the answer to Vertex-Cover on (G,k) is YES then
the answer for Set-Cover on f(G,k) is YES
􏰄 If a set W of k vertices covers all edges then the collection {Sv | v∈ W} of k sets covers all of U
􏰄 If the answer to Set-Cover on f(G,k) is YES then the answer for Vertex-Cover on (G,k) is YES
􏰄 If a subcollection Sv1,…,Svk covers all of U then the set {v1,…,vk} is a vertex cover in G.
15

Decision problems
􏰄 Computational complexity usually analyzed using decision problems
􏰄 answer is just 1 or 0 (yes or no).
􏰄 Why?
􏰄 much simpler to deal with
􏰄 deciding whether G has a path from s to t, is certainly no harder than finding a path from s to t in G, so a lower bound on deciding is also a lower bound on finding
􏰄 Less important, but if you have a good decider, you can often use it to get a good finder.
16

Polynomial time
􏰄 Define P (polynomial-time) to be
􏰄 the set of all decision problems solvable by algorithms whose worst-case running time is bounded by some polynomial in the input size.
􏰄 Many decision problems are not known to be in P
􏰄 e.g. decisionTSP:
􏰄 Given a weighted graph G and an integer k, does there exist a tour that visits all vertices in G having total weight ≤ k?
17

Satisfiability
􏰄 Boolean variables x1,…,xn
􏰄 taking values in {0,1}. 0=false, 1=true
􏰄 Literals
􏰄 xi or ¬xi for i=1,…,n
􏰄 Clause
􏰄 a logical OR of one or more literals 􏰄 e.g.(x1∨¬x3 ∨x7 ∨x12)
􏰄 CNF formula
􏰄 a logical AND of a bunch of clauses
􏰄 k-CNF formula
􏰄 All clauses have exactly k (distinct) variables
18

Satisfiability
􏰄 CNF formula example
(x1 ∨ ¬x3 ∨ x4) ∧ ( x2 ∨ ¬x4 ∨ x3) ∧ ( x2 ∨ ¬x1 ∨ x3)
􏰄 If there is some assignment of 0’s and 1’s to the variables that makes it true then we say the formula is satisfiable
􏰄 the one above is, the following isn’t 􏰄 x1 ∧ (¬x1 ∨ x2) ∧ (¬x2 ∨ x3) ∧ ¬x3
􏰄 3-SAT: Given a CNF formula F with 3 variables per clause, is it satisfiable?
19

Common property of these problems
􏰄 There is a special piece of information, a short certificate or proof, that allows you to efficiently verify (in polynomial-time) that the YES answer is correct. This certificate might be very hard to find
􏰄 e.g.
􏰄 DecisionTSP: the tour itself,
􏰄 Independent-Set, Clique: the set U
􏰄 3-SAT: an assignment that makes F true.
20

The complexity class NP
NP consists of all decision problems where
􏰄 You can verify the YES answers efficiently (in polynomial time) given a short (polynomial-size) certificate/proof
And
􏰄 No certificate/proof can fool your polynomial time verifier into saying YES for a NO instance
21

More Precise Definition of NP
􏰄 A decision problem is in NP iff there is a polynomial time procedure verify(.,.), and an integer k such that
􏰄 for every input x to the problem that is a YES instance there is a certificate t with |t| ≤ |x|k such that verify(x,t) = YES
and
􏰄 for every input x to the problem that is a NO instance there does not exist a certificate t with |t| ≤ |x|k such that verify(x,t) = YES
22

Solving NP problems without certificates
􏰄 The only obvious algorithm for most of these problems is brute force:
􏰄 try all possible certificates and check each one to see if it works.
􏰄 Exponential time:
􏰄 2n truth assignments for n variables
􏰄 n! possible TSP tours of n vertices n
􏰄   possible k element subsets of n vertices k
􏰄 etc.
23

P is contained in NP
􏰄 For a problem in P the verify procedure can be written to simply ignore its certificate
􏰄 Note: Saying that a problem is an NP problem means that it is easy to check solutions. It does NOT mean that the problem is hard.
24

Problems in NP that seem hard
􏰄 Some examples in NP 􏰄 3-SAT
􏰄 Independent-Set 􏰄 Clique
􏰄 Vertex Cover
􏰄 All hard to solve; certificates seem to help on all
􏰄 Fast solution to any gives fast solution to all of them
25

NP-hardness & NP-completeness
􏰄 Alternative approach to proving problems not in P
􏰄 show that they are at least as hard as any problem in NP
􏰄 Rough definition:
􏰄 A problem is NP-hard iff it is at least as hard as
any problem in NP
􏰄 A problem is NP-complete iff it is both
􏰄 NP-hard 􏰄 in NP
26

P and NP
NP
NP-complete
NP-hard
P
27

NP-hardness & NP-completeness
􏰄 Definition: A problem B is NP-hard iff every problem A∈NP satisfies A ≤PB
􏰄 Definition: A problem B is NP-complete iff A is NP-hard and A ∈NP
􏰄 Even though we seem to have lots of hard problems in NP it is not obvious that such super-hard problems even exist!
28

Cook-Levin Theorem
􏰄 Theorem (Cook 1971, Levin 1973): 3-SAT is NP-complete
􏰄 Recall
􏰄 CNF formula
􏰄
(x1 ∨ ¬x3 ∨ x4) ∧ ( x2 ∨ ¬x4 ∨ x3) ∧ ( x2 ∨ ¬x1 ∨ x3)
􏰄 If there is some assignment of 0’s and 1’s to the variables that makes it true then we say the formula is satisfiable
􏰄 3-SAT: Given a 3-CNF formula F, is it satisfiable?
29

Implications of Cook-Levin Theorem?
􏰄 There is at least one interesting problem in NP that captures the hardest NP problems
􏰄 Is that such a big deal? 􏰄 YES!
􏰄 There are lots of other problems that can be solved if we had a polynomial-time algorithm for 3- SAT
􏰄 Many of these problems are exactly as hard as 3- SAT
30

A useful property of polynomial-time reductions
􏰄 Theorem: If A ≤PB and B ≤PC then A ≤PC
􏰄 Proof idea: (Using ≤1 ) P
􏰄 Compose the reduction f from A to B with the reduction g from B to C to get a new reduction h(x)=g(f(x)) from A to C.
􏰄 Only work is to show the time bound since the reduction f may increase the input size for the reduction g
􏰄 Uses the fact that the composition of two polynomials is also a polynomial
􏰄 The general case is similar
31

Cook-Levin Theorem & Implications
􏰄 Theorem (Cook 1971, Levin 1973): 3-SAT is NP-complete
􏰄 Proof:
For proof see CSE 531
􏰄 Corollary: B is NP-hard ⇔ 3-SAT ≤PB 􏰄 (or A ≤PB for any NP-complete problem A)
􏰄 If B is NP-hard then every problem in NP polynomial-time reduces to B, in particular 3-SAT does since it is in NP
􏰄 For any problem A in NP, A ≤P3-SAT and so if 3-SAT ≤PB we have A ≤P B.
􏰄 therefore B is NP-hard if 3-SAT ≤PB
32

Another NP-complete problem:
3-SAT ≤PIndependent-Set
􏰄 A Tricky Reduction:
􏰄 mapping CNF formula F to a pair (G,k) 􏰄 Let m be the number of clauses of F
􏰄 Create a vertex in G for each literal in F 􏰄 Join two vertices u, v in G by an edge iff
􏰄 u and v correspond to literals in the same clause of F, (green edges) or
􏰄 u and v correspond to literals x and ¬x (or vice versa) for some variable x. (red edges).
􏰄 Set k=m
􏰄 Clearly polynomial time
33

F:
3-SAT ≤PIndependent-Set
(x1 ∨ ¬x3 ∨ x4) ∧ ( x2 ∨ ¬x4 ∨ x3) ∧ ( x2 ∨ ¬x1 ∨ x3)
x1 x2 ¬x3 ¬x4
x2 ¬x1
x4 x x3 3
34

3-SAT ≤PIndependent-Set 􏰄 Correctness:
􏰄 If F is satisfiable then there is some assignment that satisfies at least one literal in each clause.
􏰄 Consider the set U in G corresponding to the first satisfied literal in each clause.
􏰄 |U|=m
􏰄 Since U has only one vertex per clause, no two vertices
in U are joined by green edges
􏰄 Since a truth assignment never satisfies both x and ¬x, U doesn’t contain vertices labeled both x and ¬x and so no vertices in U are joined by red edges
􏰄 Therefore G has an independent set, U, of size at least m
􏰄 Therefore (G,m) is a YES for independent set.
35

3-SAT ≤PIndependent-Set 101101101
F: (x1 ∨ ¬x3 ∨ x4) ∧ ( x2 ∨ ¬x4 ∨ x3) ∧ ( x2 ∨ ¬x1 ∨ x3)
U
x1 x2 ¬x3 ¬x4
x2 ¬x1
x4 x x3 3
Given assignment x1=x2=x3=x4=1, U is as circled
36

3-SAT ≤PIndependent-Set 􏰄 Correctness continued:
􏰄 If (G,m) is a YES for Independent-Set then there is a set U of m vertices in G containing no edge.
􏰄 Therefore U has precisely one vertex per clause because of the green edges in G.
􏰄 Because of the red edges in G, U does not contain vertices labeled both x and ¬x
􏰄 Build a truth assignment A that makes all literals labeling vertices in U true and for any variable not labeling a vertex in U, assigns its truth value arbitrarily.
􏰄 By construction, A satisfies F 􏰄 Therefore F is a YES for 3-SAT.
37

F:
(x1 ∨ ¬x3 ∨ x4) ∧ ( x2 ∨ ¬x4 ∨ x3) ∧ ( x2 ∨ ¬x1 ∨ x3)
3-SAT ≤PIndependent-Set 010?10?10
x1 x2 ¬x3 ¬x4
x2 ¬x1
x4 x x3 3
Given U, satisfying assignment is x1=x3=x4=0, x2=0 or 1
38

Independent-Set is NP-complete
􏰄 We just showed that Independent-Set is NP- hard and we already knew Independent-Set is in NP.
􏰄 Corollary: Clique is NP-complete
􏰄 We showed already that Independent-Set ≤P Clique and Clique is in NP.
39

Problems we already know are NP- complete
􏰄 3-SAT
􏰄 Independent-Set
􏰄 Clique
􏰄 Vertex-Cover
􏰄 Set-Cover
􏰄 10,000’s of practical problems that are NP-complete, e.g. scheduling, optimal VLSI layout etc.
40

Steps to Proving Problem B is NP-complete
􏰄 Show B is NP-hard:
􏰄 State:”Reduction is from NP-hard Problem A”
􏰄 Show what the map f is
􏰄 Argue that f is polynomial time
􏰄 Argue correctness: two directions Yes for A implies Yes for B and vice versa.
􏰄 Show B is in NP
􏰄 State what certificate is and why it works 􏰄 Argue that it is polynomial-time to check.
41

Some other NP-complete examples you should know
􏰄 Hamiltonian-Cycle Given a directed graph G is there a cycle in G that visits each vertex in G exactly once?
􏰄 Hamiltonian-Path Given a directed graph G is there a path in G that visits each vertex in G exactly once?
􏰄 Both are also NP-complete when G is an undirected graph
􏰄 Note that deciding the similar questions for Eulerian- Cycle and Eulerian-Path (which require that each edge be visited exactly once rather than each vertex) can be done in polynomial time.
􏰄 How?
42

Travelling-Salesman Problem (TSP)
􏰄 Given a set of n cities v1,…,vn and distances between each pair of cities d(vi,vj) what is the shortest tour that visits all the cities?
􏰄 Not a decision problem
􏰄 DecisionTSP:
􏰄 Given a set of distances given by d for each pair of cities in v1,…,vn and an integer D, does there exist a tour that visits all cities having total weight at most D?
43

Hamiltonian-Cycle≤PDecisionTSP 􏰄 Define the reduction
􏰄 Vertices V of G=(V,E) become cities 􏰄 Set d(vi,vj) to 1 if (vi,vj)∈E
􏰄 Set D=|V|
2 if not
􏰄 Claim: There is a Hamiltonian cycle in G iff there is a tour of length |V|
44

Graph Colorability
􏰄 Defn: Given a graph G=(V,E), and an integer k, a k-coloring of G is
􏰄 anassignmentofuptokdifferentcolorstothe vertices of G so that the endpoints of each edge have different colors.
􏰄 3-Color: Given a graph G=(V,E), does G have a 3-coloring?
􏰄 Claim: 3-Color is NP-complete 􏰄 Proof: 3-Color is in NP:
􏰄 Certificate is an assignment of red,green,blue to the vertices of G
􏰄 Easy to check that each edge is colored correctly
45

3-SAT ≤P3-Color 􏰄 Reduction:
􏰄 We want to map a 3-CNF formula F to a graph G so that
􏰄 G is 3-colorable iff F is satisfiable
46

3-SAT ≤P3-Color
F
T
Base Triangle
O
47

¬x1
3-SAT ≤P3-Color
¬x2 x1
in 3-coloring, variable colors correspond to some truth assignment (same color as T or F)
… x2
¬xn
Variable Part:
F
T
xn
O
48

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
x1 ¬x1
O
3-SAT ≤P3-Color
x2 ¬x2
¬xn …
xn
F
T
Clause Part:
Add one 6 vertex gadget per clause connecting its ‘outer vertices’ to the literals in the clause
49

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
3-SAT ≤P3-Color
¬xxn FT
¬x2 x1
O
¬x1
n x2
F O

O
F
T
Any truth assignment satisfying the formula can be extended to a 3-coloring of the graph
O
50

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
x1 ¬x1
O
3-SAT ≤P3-Color ¬x xn
F
x2 ¬x2
n …
T
O
F
T
Any 3-coloring of the graph colors each gadget triangle using each color
51

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
x1 ¬x1
O
3-SAT ≤P3-Color ¬x xn
F
x2 ¬x2
n …
T
O F
F
T
Any 3-coloring of the graph has an F opposite the O color in the triangle of each gadget
52

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
x1 ¬x1
O
3-SAT ≤P3-Color ¬x xnT
F
x2 ¬x2
n …
T
O F
F
T
Any 3-coloring of the graph has T at the other end of the blue edge connected to the F
53

(x1 ∨ x3 ∨ x6)
(¬x1 ∨ x2 ∨ xn)
x1 ¬x1
O
3-SAT ≤P3-Color ¬x xnT
F
x2 ¬x2
n …
T
O F
F
T
Any 3-coloring of the graph yields a satisfying assignment to the formula
54

More NP-completeness
􏰄 Subset-Sum problem
􏰄 Given n integers w1,…,wn and integer W
􏰄 Is there a subset of the n input integers that adds up to exactly W?
􏰄 O(nW) solution from dynamic programming but if W and each wi can be n bits long then this is exponential time
55

3-SAT ≤PSubset-Sum
􏰄 Given a 3-CNF formula with m clauses
and n variables
􏰄 Will create 2m+2n numbers that are
m+n digits long
􏰄 Two numbers for each variable xi
􏰄 ti and fi (corresponding to xi being true or xi being false)
􏰄 Two extra numbers for each clause
􏰄 uj and vj (filler variables to handle number of false literals in clause Cj)
56

3-SAT ≤PSubset-Sum ij
u1=v1 u2=v2
0000… 0 1000…0
W
1111… 1 3333…3
1234… n 1234…m
C3=(x1∨¬ x2∨ x5)
t1 1000… 0 0010…1 f1 1000… 0 1001…0
0100… 0 0100…1 f2 0100… 0 0011…0
t2
… ….
0000… 0 0100…0 … ….
57

Matching Problems
􏰄 Perfect Bipartite Matching
􏰄 Given a bipartite graph G=(V,E) where V=X∪Y and E ⊆ X × Y, is there a set M in E such that every vertex in V is in precisely one edge of M ?
􏰄 In P
􏰄 Network Flow gives O(nm) algorithm where n=|V|, m=|E|.
58

3-Dimensional Matching
􏰄 Perfect Bipartite Matching is in P
􏰄 Given a bipartite graph G=(V,E) where V=X∪Y and E ⊆ X × Y, is there a subset M in E such that every vertex in V is in precisely one edge of M ?
􏰄 3-Dimensional Matching
􏰄 Given a tripartite hypergraph G=(V,E) where V=X∪Y∪Z and E ⊆ X × Y× Z, is there a subset M in E such that every vertex in V is in precisely one hyperedge of M ?
􏰄 is in NP: Certificate is the set M
59

3-Dimensional Matching
􏰄 Theorem: 3-Dimensional Matching is NP-complete
􏰄 Proof:
􏰄 We’ve already seen that it is in NP
􏰄 3-Dimensional Matching is NP-hard:
􏰄 Reduction from 3-SAT
􏰄 Given a 3-CNF formula F we create a tripartite hypergraph (“hyperedges” are triangles) G based on F as follows
60

3-SAT ≤P 3-Dimensional Matching 􏰄 Variable part:
􏰄 If variable xi occurs ri times in F create ri red and ri green triangles linked in a circle, one pair per occurrence
􏰄 Perfect matching M must either use all the green edges leaving red tips uncovered (xi is assigned false) or all the red edges leaving all green tips uncovered (xi is assigned true)
61

3-SAT ≤P 3-Dimensional Matching 􏰄 Clause part: Two new nodes per clause joined to
each of its literals:
C3=(x1∨¬ x2∨ x5)
x1
x2
x5
62

3-SAT ≤P 3-Dimensional Matching
􏰄 Slack: If there are m clauses then there are 3m variable occurrences. That means 3m total tips are not covered by whichever of red or green triangles not chosen. Of these, m are covered if each clause is satisfied. Need to cover the remaining 2m tips.
Solution: Add 2m pairs of slack vertices Add triangles joining each pair with every tip!
63

3-SAT ≤P 3-Dimensional Matching 􏰄 Well-formed: Each triangle has one of each
type of node:
􏰄 Correctness:
􏰄 If F has a satisfying assignment then choose the following triangles which form a perfect 3-dimensional matching in G:
􏰄 Either the red or the green triangles in the cycle for xi – the opposite of the assignment to xi
􏰄 The triangle containing the first true literal for each clause and the two clause nodes
􏰄 2m slack triangles one per new pair of nodes to cover all the remaining tips
64

3-SAT ≤P 3-Dimensional Matching 􏰄 Correctness continued:
􏰄 If G has a perfect 3-dimensional matching then:
􏰄 Each blue node in the cycle for each xi is contained in exactly two triangles, exactly one of which much be in M. If one triangle in the cycle is in M, the others must be the same color. We use the color not used to define the truth assignment to xi
􏰄 The two nodes for any clause must be contained in an edge which must also contain a third node that corresponds to a literal made true by the truth assignment. Therefore the truth assignment satisfies F so it is satisfiable.
65