# CS代考程序代写 algorithm computational biology distributed system Lecture 11 cont’d:

Lecture 11 cont’d:

NP and Computational Intractability

The University of Sydney

Page 1

Definition of the class NP

Class NP: Decision problems for which YES-instances have a poly-time certifier.

Certification algorithm intuition.

– Certifier views things from “managerial” viewpoint.

– Certifier does not solve the problem by its own;

rather, it checks if a proposed proof t is a valid solution.

Definition: Algorithm C(s,t) is a certifier for problem X if for every input instance s and proposed proof t, C(s, t) = `yes’ if and only if t is a valid solution to s.

“certificate” or “witness”

The University of Sydney

Page 2

Certifiers and Certificates: 3-Satisfiability

SAT: Given a CNF formula F, is there a satisfying assignment? Certificate: An assignment of truth values to the n boolean variables. Certifier: Check that each clause in F has at least one true literal.

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) instance s

Conclusion: SAT is in NP. The University of Sydney

Page 3

x1,x2,x4=true, x3=false certificate t

Class NP-hard

Class NP-complete: A problem in NP such that every problem in NP polynomially reduces to it.

Class NP-hard:

A decision problem such that every problem in NP polynomially reduces to it.

not necessarily in NP

The University of Sydney

Page 4

Establishing NP-Completeness

Remark: Once we establish first “natural” NP-complete problem, others fall like dominoes.

Recipe to establish NP-completeness of problem Y. – Step1. ShowthatYisinNP.

– Step 2. Choose an NP-complete problem X. – Step 3. Prove that X £ p Y.

Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X £ P Y then Y is NP-complete.

Proof: LetWbeanyprobleminNP. ThenW £P X £P Y. – Bytransitivity,W£P Y.

– Hence Y is NP-complete. ▪ The University of Sydney

by definition of NP-complete

by assumption

Page 5

Reduction Template for Decision Problems (aka Karp reduction)

Algorithm for X

Instance of Y

f(I)

Yes for f(I) No for f(I)

Transforms instance of X to instance of Y

Algorithm for Y

Instance of X

I

Yes for I No for I

Step 2

Step 1

Step 1: Construct a polynomial-time algorithm that transforms instance I of X to an instance f(I) of Y

Step 2: Prove correctness, which boils down to showing

Answer for I is Yes iff answer for f(I) is Yes

Proof usually done by transforming certificate for I to certificate

for f(I) and vice versa The University of Sydney

Page 6

Summary – Lecture 11

§ Polynomial time reductions

3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVER VERTEX-COVER £P SUBSET-SUM

§ Complexity classes:

P: Decision problems for which there is a poly-time algorithm. NP: Decision problems for which there is a poly-time certifier.

NP-complete: A problem in NP such that every problem in NP polynomial reduces to it.

NP-hard: A problem such that every problem in NP polynomial reduces to it.

§ Lots of problems are NP-complete

See https://www.nada.kth.se/~viggo/wwwcompendium/

The University of Sydney

Page 7

Partitioning Problems

Six basic genres

§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.

§ Constraint satisfaction problems: SAT, 3-SAT.

§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.

3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.

§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of Sydney

Page 8

Graph Coloring

Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.

Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?

A complete graph on n vertices require at least n colors. (Proof by induction.) The University of Sydney

Page 9

Graph Coloring

Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.

Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?

1 1′ 2 2′

3 3′

The University of Sydney

Page 10

Graph Coloring

Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.

Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?

1 1′ 2 2′

3 3′

A graph can be colored with at most 2 colors iff it is bipartite The University of Sydney

Page 11

Graph Coloring

k-COLOR: Given an undirected graph G = (V, E) with n vertices, does there exist a proper coloring using at most k colors?

k-COLOR is in NP:

– certificate = k-coloring,

– certifying algorithm checks that it is a proper coloring and uses at most k colors

1 1′ 2 2′

3 3′

2-COLOR is equivalent to testing for bipartiteness and so is in P. 1-COLOR and n-COLOR is also in P (why?)

The University of Sydney

Page 12

3-SAT Reduces to 3-COLOR

3-COLOR: Given an undirected graph G = (V, E), does there exist a proper coloring using at most 3 colors?

Theorem: 3-SAT £P 3-COLOR.

The University of Sydney Page 13

3-SAT Reduces to 3-COLOR

Theorem: 3-SAT £P 3-COLOR.

Proof: Given an arbitrary instance F of 3-SAT, we construct an instance G of 3-

COLOR that has a 3-coloring iff F is satisfiable. Construction of G:

1. Truth gadget. Introduce 3 special vertices called T, F and O connected to each other. Call their colors T, F and O.

2. Variable gadget. Introduce 2 literal vertices per variable and connect them to each other and O. Literals with same color as T is assigned true, those with same color as F is assigned false. Thus, 3-coloring = consistent truth assignment (every variable is either true or false).

O

TF

The University of Sydney

x1 x1

Page 14

3-SAT Reduces to 3-COLOR

Construction of G:

3.

– –

Clause gadget.

For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.

Suppose both left and middle variable vertices colored with F.

T

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4)

The University of Sydney x1 x2 x3 Page 15

3-SAT Reduces to 3-COLOR

Construction of G:

3.

– –

Clause gadget.

For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.

Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.

T

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) TO

FF

The University of Sydney x1 x2 x3 Page 16

3-SAT Reduces to 3-COLOR

Construction of G:

3.

– –

Clause gadget.

For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.

Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.

T

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F

TO

FF

The University of Sydney x1 x2 x3 Page 17

3-SAT Reduces to 3-COLOR

Construction of G:

3.

– –

Clause gadget.

For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.

Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.

T

OF

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F

TO

FF

The University of Sydney x1 x2 x3 Page 18

3-SAT Reduces to 3-COLOR

Construction of G:

3.

– –

Clause gadget.

For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.

Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors. In particular, the right

variable vertex must be colored T.

T

OF

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F

TO

FF

T

The University of Sydney x1 x2 x3 Page 19

3-SAT Reduces to 3-COLOR

Claim: For each clause gadget, a coloring of variable vertices using T and F colors can be extended to a proper 3-coloring of the entire gadget iff at least one variable vertex is colored T.

Proof:

Þ Done in previous slide.

Ü Check all 7 such colorings by hand.

T

OF

(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F

TO

FF

T

The University of Sydney x1 x2 x3 Page 20

3-SAT Reduces to 3-COLOR

Claim: G has a 3-coloring iff F is satisfiable.

Proof: Þ Suppose G has a 3-coloring.

– Assign literals with same color as vertex T true, rest is false.

– We have argued previously that assignment is consistent and every clause has at least one true literal.

Ü Suppose F has a satisfying assignment.

– Color literal vertices and truth gadget accordingly.

– For each clause gadget, can extend to a proper 3-coloring if at least one literal vertex is set to true.

Truth Gadget

The University of Sydney

Variable Gadget

Clause Gadget

Page 21

Lecture 11:

Coping with hardness

The University of Sydney

Page 22

Algorithms and hardness

Algorithmic techniques:

– Greedy algorithms [Lecture 3]

– Divide & Conquer algorithms [Lectures 4 and 5]

– Dynamic programming algorithms [Lectures 6 and 7]

– Network flow algorithms [Lectures 8 and 9]

Hardness:

– NP-hardness [Lectures 10 and 11]: O(nc) algorithm is unlikely

Today

– How can we cope with hard problems? The University of Sydney

Page 23

Algorithms and hardness

Lots of problems that we can solve efficiently:

– MST

– Shortest path

– Scheduling

– Max flow –…

But lots of problems that we can’t solve efficiently:

– All NP-complete problems: O(nc) algorithm is unlikely vertex cover, independent set, 3-SAT,…

– But what if we need to solve an NP-complete problem? The University of Sydney

Page 24

Cope with NP-complete problems?

The University of Sydney Page 25

Cope with NP-complete problems?

• Heuristics: Local search, simulated annealing, neural networks…

• Randomized algorithms: Not always correct, but a probability is

guaranteed.

• Approximation algorithms: Not optimal solution, but within a guaranteed

error.

• Fixed-parameter algorithms: Algorithms whose complexity depends on

other parameters than n.

• Efficient exact algorithms: Euclidean TSP

• Restricted instance: trees, bipartite graphs…

The University of Sydney

Page 26

Coping With NP-Completeness

Question: What should I do if I need to solve an NP-complete problem?

Answer: Theory says you’re unlikely to find poly-time algorithm.

Must sacrifice one of three desired features. – Solve problem to optimality.

• Approximation algorithms

• Randomized algorithms

– Solve problem in polynomial time.

• Exact exponential time algorithms

– Solve arbitrary instances of the problem.

• Solve restricted classes of instances • Parametrized algorithms

The University of Sydney

Page 27

10.1 Solving restricted instances

For example in the case when the vertex cover is small.

The University of Sydney Page 28

10.1 Finding Small Vertex Covers

VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.

16 27

38 49

5 10

k=4

S = { 3, 6, 7, 10 }

The University of Sydney

Page 29

Vertex Cover

VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.

Vertex Cover (or Independent Set) arises naturally in many applications:

– dynamic detection of race conditions (distributed systems).

– computational biology

– Biochemistry

– Pattern recognition

– Computer vision –…

What should we do if we need to solve it?

The University of Sydney

Page 30

Finding Small Vertex Covers

Question: What if k is small?

Brute force: O(knk+1).

– Try all nk Î O(nk) subsets of size k.

– Takes O(kn) time to check whether a subset is a vertex cover.

The University of Sydney

Page 31

Finding Small Vertex Covers

Question: What if k is small?

Brute force: O(knk+1).

– Try all nk Î O(nk) subsets of size k.

– Takes O(kn) time to check whether a subset is a vertex cover.

Aim: Limit exponential dependency on k, e.g., to O(2k kn).

Example: n = 1000, k = 10.

– Brute force. knk+1 = 1034 Þ infeasible. – Better. 2k kn = 107 Þ feasible.

Remark. If k is a constant, algorithm is poly-time; if k is a small constant, then it’s also practical.

The University of Sydney

Page 32

Finding Small Vertex Covers

Theorem: Let (u,v) be an edge of G. G has a vertex cover of size £ k iff at least one of G{u} and G{v} has a vertex cover of size £ k-1.

delete u and all incident edges

uv

The University of Sydney

Page 33

Finding Small Vertex Covers

Theorem: Let (u,v) be an edge of G. G has a vertex cover of size £ k iff at least one of G{u} and G{v} has a vertex cover of size £ k-1.

delete u and all incident edges

Proof:

uv

Þ

– Suppose G has a vertex cover S of size £ k.

– S contains either u or v (or both). Assume it contains u. – S{u} is a vertex cover of G{u}.

G{u}

The University of Sydney

Page 34

Finding Small Vertex Covers

Theorem: Let (u,v) be an edge of G. G has a vertex cover of size £ k iff at least one of G{u} and G{v} has a vertex cover of size £ k-1.

delete u and all incident edges

Proof:

uv

Þ

– Suppose G has a vertex cover S of size £ k.

– S contains either u or v (or both). Assume it contains u.

– S{u} is a vertex cover of G{u}. Ü

– Suppose S is a vertex cover of G{u} of size £ k-1.

– ThenSÈ{u}isavertexcoverofGofsizek. ▪

G{u}

The University of Sydney

Page 35

Finding Small Vertex Covers

Theorem: Let (u,v) be an edge of G. G has a vertex cover of size £ k iff at least one of G{u} and G{v} has a vertex cover of size £ k-1.

delete u and all incident edges

Proof:

uv

Þ

– Suppose G has a vertex cover S of size £ k.

– S contains either u or v (or both). Assume it contains u.

– S{u} is a vertex cover of G{u}. Ü

– Suppose S is a vertex cover of G{u} of size £ k-1.

– ThenSÈ{u}isavertexcoverofGofsizek. ▪

G{u}

Observation: If G has a vertex cover of size k, it has £ k(n-1) edges. Proof: Each vertex covers at most n-1 edges. ▪

The University of Sydney

Page 36

Finding Small Vertex Covers: Algorithm

Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.

uv

G,k

G{u} k-1

boolean Vertex-Cover(G,k) {

if (G contains no edges) return true

if (G contains > k(n-1) edges) return false

let (u,v) be any edge of G

a = Vertex-Cover(G{u},k-1)

b = Vertex-Cover(G{v},k-1)

return a or b

}

The University of Sydney

Page 37

Finding Small Vertex Covers: Algorithm

Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.

uv

G,k

boolean Vertex-Cover(G,k) {

if (G contains no edges) return true

if (G contains > k(n-1) edges) return false

let (u,v) be any edge of G

a = Vertex-Cover(G{u},k-1)

b = Vertex-Cover(G{v},k-1)

return a or b

}

G{u} k-1

G{v}

k-1 £k

The University of Sydney

Page 38

Finding Small Vertex Covers: Algorithm

Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.

boolean Vertex-Cover(G,k) {

if (G contains no edges) return true

if (G contains > k(n-1) edges) return false

let (u,v) be any edge of G

a = Vertex-Cover(G{u},k-1)

b = Vertex-Cover(G{v},k-1)

return a or b

}

uv

G,k

G{u} k-1

G{v}

k-1 £k

Proof:

– Correctness follows from previous two claims and induction on k. – There are £ 2k+1 nodes in the recursion tree; each invocation

takes O(kn) time. ▪ The University of Sydney

Page 39

Finding Small Vertex Covers: Algorithm

Theorem: Vertex cover can be solved in O(2k kn) time. This is fine as long as k is (a small) constant.

What if k is not a small constant?

uv

G,k

G{u} k-1

G{v}

k-1 £k

The University of Sydney

Page 40

10.2 Solving NP-Hard Problems on restricted input instances

For example special cases of graphs: – trees,

– bipartite graphs,

– planar graphs,

–…

The University of Sydney

Page 41

Independent Set on Trees

INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?

Problem: Given a tree, find a maximum IS. Key observation: If v is a leaf, there exists

a maximum size independent set containing v. Proof: [exchange argument]

u v

– Consider a max cardinality independent set S.

– IfvÎS,we’redone.

– IfuÏSandvÏS,thenSÈ {v}isindependentÞSnotmaximum. – IF u Î S and v Ï S, then S È {v}/{u} is independent. (exchange) ▪

The University of Sydney

Page 42

Independent Set on Trees: Greedy Algorithm

Theorem: The following greedy algorithm finds a maximum cardinality independent set in forests (and hence trees).

u v

Independent-Set-In-A-Forest(F) { S¬Æ

while (F has at least one edge) {

Let e = (u,v) be an edge such that v is a leaf

Add v to S

Delete from F nodes u and v, and all edges

incident to them.

}

Add remaining vertices to S

return S }

ß

u v

ß

Proof: Correctness follows from the previous key observation. ▪

Remark. Can implement in O(n) time by considering nodes in postorder. The University of Sydney

Page 43

Independent Set on Trees

INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?

Problem: Given a tree, find a maximum IS. Theorem:

INDEPENDENT-SET on trees can be solved in O(n) time.

Corollary:

VERTEX-COVER on trees can be solved in O(n) time.

u v

The University of Sydney

Page 44

Weighted Independent Set on Trees

Weighted independent set on trees. Given a tree and node weights wv > 0, find an independent set S that maximizes SvÎS wv.

r

u vwx

children(u) = { v, w, x }

The University of Sydney

Page 45

Weighted Independent Set on Trees

Weighted independent set on trees. Given a tree and node weights wv > 0, find an independent set S that maximizes SvÎS wv.

Observation: If (u, v) is an edge such that v is a leaf node, then either OPT includes u, or it includes all leaf nodes incident to u.

r

u vwx

children(u) = { v, w, x }

The University of Sydney

Page 46

Weighted Independent Set on Trees

Weighted independent set on trees. Given a tree and node weights wv > 0, find an independent set S that maximizes SvÎS wv.

Observation: If (u, v) is an edge such that v is a leaf node, then either OPT includes u, or it includes all leaf nodes incident to u.

Dynamic programming solution: Root tree at some node, say r. – OPTin(u) = max weight independent set

rooted at u, containing u.

– OPTout(u) = max weight independent set rooted at u, not containing u.

r

u vwx

children(u) = { v, w, x }

OPTin(u) = wu + å OPTout(v) v Î children(u)

OPTout (u) = å max {OPTin (v), OPTout (v)} v Î children(u)

The University of Sydney

Page 47

Weighted Independent Set on Trees: Dynamic Programming

Theorem: The dynamic programming algorithm find a maximum weighted independent set in trees in O(n) time.

u

Weighted-Independent-Set-In-A-Tree(T) {

Root the tree at a node r

foreach (node u of T in postorder) {

if (u is a leaf) { Min [u] = wu

Mout[u] = 0} else {

Min [u] = SvÎchildren(u) Mout[v]+wv

Mout[u] = SvÎchildren(u) max(Mout[v],Min[v])}

}

return max(Min[r], Mout[r]) }

u

Proof: Takes O(n) time since we visit nodes in postorder and examine each edge exactly once. ▪

The University of Sydney

Page 48

Approximation Algorithms

Sacrifice optimality, but still run in polynomial time.

Approximation ratio =

Cost of apx solution Cost of optimal solutions

An approximation algorithm for a minimization problem requires an approximation guarantee:

• Approximation ratio ≤ c

• Approximation solution ≤ c · value of optimal solution

The University of Sydney

Page 73

Vertex Cover

The University of Sydney Page 74

Vertex Cover

Optimization version: Given an undirected graph G = (V, E), find the smallest vertex cover C.

First try: Pick an edge e = (u,v) that is uncovered. Choose one of u and v to add to cover. Repeat.

On a star graph, approximation factor is 𝛀(n)! Example: Star graph with 4 vertices

The University of Sydney

Page 75

Vertex Cover

Weak duality: Let M be a matching, and let C be a vertex cover. Then, |M| £ |C|.

Proof: Each vertex can cover at most one edge in any matching. 1 1′

2 2′

3 3′ 4 4′

5 5′

M = 1-2′, 3-1′, 4-5′ |M| = 3

The University of Sydney

Page 76

Vertex Cover

Weak duality: Let M be a matching, and let C be a vertex cover. Then, |M| £ |C|.

Greedy algorithm:

– Initialise S = empty set

– While there exists an edge e = (u,v) not covered by S:

– AddbothuandvtoS Thm: S is a 2-approximation.

Proof:

– Let M be set edges encountered in while loop. This is a matching.

– Let C* be smallest vertex cover.

– |S| = 2|M| £ 2|C*|.

Not known how to do better! 7/6 is NP-hard. The University of Sydney

Page 77

Randomization

Randomization: Allow fair coin flip in unit time.

Why randomize? Can lead to simplest, fastest, or only known algorithm for a

particular problem.

Example: Symmetry breaking protocols, graph algorithms, quicksort, hashing, load balancing, Monte Carlo integration, cryptography.

The University of Sydney Page 85

13.4 MAX 3-SAT

The University of Sydney Page 86

Maximum 3-Satisfiability

MAX-3SAT: Given 3-SAT formula, find a truth assignment that satisfies as many

clauses as possible.

C1 =x2Úx3Úx4 C2 =x2Úx3Úx4 C3 =x1Úx2Úx4 C4 =x1Úx2Úx3 C5 =x1Úx2Úx4

Remark. NP-hard search problem.

Simple idea: Flip a coin, and set each variable true with probability 1⁄2,

independently for each variable. The University of Sydney

Page 87

Maximum 3-Satisfiability: Analysis

Theorem: Given a 3-SAT formula with k clauses, the expected number of clauses satisfied by a random assignment is 7k/8.

Proof: Consider random variable Zj = ìí1 if clause Cj is satisfied î 0 otherwise.

Let Z = number of clauses satisfied by the assignment Þ linearity of expectation

E[Z] = åk E[Zj] j=1

= åk Pr[clause C j is satisfied] j=1

= 78 k

Z=Z1+Z2+Z3+…+Zk

E[Zi] = Probability that (x Ú y Ú z) is not satisfied?

1⁄2 · 1⁄2 · 1⁄2 = 1/8

The University of Sydney

Page 88

The Probabilistic Method

Corollary: For any instance of 3-SAT, there exists a truth assignment that satisfies at least a 7/8 fraction of all clauses.

Proof: There must be an assignment that performs at least as well as the expectation! ▪

Remark: Any 3-SAT instance with at most 7 clauses must always be satisfiable.

Probabilistic method: We showed the existence of a non-obvious property of 3-SAT by showing that a random construction produces it with positive probability!

Hardness of Approximation: NP-hard to do better than 7/8!

The University of Sydney Page 89

Summary

NP-complete problems show up in many applications. There are different approaches to cope with it:

• Approximation algorithms

• Restricted cases (trees, bipartite graphs, small solution…)

• Randomized algorithms •…

Each approach has its pros and cons.

The University of Sydney Page 92