CS代考程序代写 algorithm computational biology distributed system Lecture 11: NP-completeness + Coping with hardness

Lecture 11: NP-completeness + Coping with hardness
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

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 3

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 4

Reduction Template for NP-Completeness Proofs
Algorithm for X
Special 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 a special 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
(⇒) Transform a YES-certificate for I into a YES-certificate for f(I)
(⇐) Transform a YES-certificate for f(I) into a YES-certificate for I The University of Sydney
Page 5

Taxonomy of NP-Complete Problems
Six Basic genres
§ Constraint satisfaction problems: SAT, 3-SAT.
§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.
§ 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 6

Vertex Cover Reduces to Subset Sum
Proof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover of size at least k.
Number edges from 0 to |E|-1. Set S of integers:
– For the i-th edge, add an integer bi
– For each vertex v, add an integer av
bi = 4i
av = 4|E| + X 4i
i:i-th edge is incident to v
|EX|1 t=k·4|E| +
2·4i
Subset-Sum can be solved in O(nT) using DP WhereT=totalsumofintegersinS
Does this mean P = NP? Page 7
The University of Sydney i=0

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 8

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 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4)
The University of Sydney x1 x2 x3 Page 9

8.5 Sequencing 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 10

Hamiltonian Cycle
HAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle G that contains every node in V.
The University of Sydney Vertices and faces of a dodecahedron: Yes Page 11

Hamiltonian Cycle
HAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle G that contains every node in V.
The University of Sydney
1 1′
2 2′
3 3′
4 4′
5
Bipartite graph with odd number of nodes: No (Why?)
Page 12

Eulerian Cycle
EULER-CYCLE: given an undirected graph G = (V, E), does there exist a cycle G that contains every edge in G.
The University of Sydney
1 1′ 2 2′
3 3′ 4 4′
5
Graph with odd-degree nodes: No
Page 13

Eulerian Cycle
EULER-CYCLE: given an undirected graph G = (V, E), does there exist a cycle G that contains every edge in G exactly once.
EULER-CYCLE is in P
Theorem G has an Eulerian cycle iff every vertex has even degree. But HAM-CYCLE and DIR-HAM-CYCLE are NP-complete!
What are the certificates?
Will show 3-SAT £ P DIR-HAM-CYCLE £ P HAM-CYCLE
The University of Sydney
Page 14

Directed Hamiltonian Cycle
DIR-HAM-CYCLE: Given a directed graph G = (V, E), does there exist a simple directed cycle G that contains every node in V?
Theorem: DIR-HAM-CYCLE £ P HAM-CYCLE.
Proof idea: Given a directed graph G = (V, E), construct an undirected graph
G’ with 3n vertices.
For each vertex v, add vertices vin, v, vout. For directed edge (u,v) , add edge (uout, vin)
a
bv c
G
aout d
din
ein
e
bout cout
vin v vout
G’
The University of Sydney
Page 15

Directed Hamiltonian Cycle
Claim: G has a Hamiltonian cycle iff G’ does.
Proof:
Þ –
– Then G’ has an undirected Hamiltonian cycle (same order).
Suppose G has a directed Hamiltonian cycle G.
Ü –
– G’ must visit nodes in G’ using one of two orders:
Suppose G’ has an undirected Hamiltonian cycle G’.
…, B, G, R, B, G, R, B, G, R, B, …
…, B, R, G, B, R, G, B, R, G, B, …
– Blue nodes in G’ make up directed Hamiltonian cycle G in G, or reverse
of one. ▪
aout
bout vin cout
din
ein
d dout
v vout G’
The University of Sydney
Page 16

3-SAT Reduces to Directed Hamiltonian Cycle
Theorem: 3-SAT £ P DIR-HAM-CYCLE.
Proof: Given an instance F of 3-SAT, we construct an instance of DIR-HAM-
CYCLE that has a Hamiltonian cycle iff F is satisfiable.
Construction. First, create graph that has 2n Hamiltonian cycles which
correspond in a natural way to 2n possible truth assignments.
The University of Sydney
Page 17

3-SAT Reduces to Directed Hamiltonian Cycle
Construction: Given a 3-SAT instance F with n variables xi and k clauses.
– Construct G to have 2n Hamiltonian cycles.
– Variable gadget: Path i corresponds to variable xi and has 3k + 3 vertices (2 endpoints, 2 vertices per clause and a filler vertex between clauses and between first/last clause and endpoint.
– Intuition: Traverse path i from left to right Û set variable xi = 1.
– Can’t skip rows!
s
x2
x3
The University of Sydney
Page 18
3k + 3
t
x1

3-SAT Reduces to Directed Hamiltonian Cycle
– Construction. Given 3-SAT instance F with n variables xi and k clauses. – For clause j: add a node and 6 edges (2 per literal)
C1 =x1 Vx2 Vx3
clause node
clause node
s
The University of Sydney
Page 19
t
C2 =x1 Vx2 Vx3
x1
x2
x3

3-SAT Reduces to Directed Hamiltonian Cycle
– Construction. Given 3-SAT instance F with n variables xi and k clauses.
– For clause j: add a node and 6 edges (2 per literal)
– If literal xi appears in clause j, add edge from 3j-th vertex of path i to clause node and from clause node to (3j+1)-th vertex of path i
– If 𝑥! appears, add edge from (3j+1)-th vertex of path i to clause node !
and from clause node to 3j-th vertex of path i
C1 =x1 Vx2 Vx3
clause node
clause node
s
The University of Sydney
Page 20
t
C2 =x1 Vx2 Vx3
x1
x2
x3

3-SAT Reduces to Directed Hamiltonian Cycle
– Construction. Given 3-SAT instance F with n variables xi and k clauses.
– For clause j: add a node and 6 edges (2 per literal)
– If literal xi appears in clause j, add edge from 3j-th vertex of path i to clause node and from clause node to (3j+1)-th vertex of path i
– If 𝑥! appears, add edge from (3j+1)-th vertex of path i to clause node !
The University of Sydney
Page 21
and from clause node to 3j-th vertex of path i
C1 =x1 Vx2 Vx3
clause node
clause node
C2 =x1 Vx2 Vx3
s
t
x1
x2
x3

3-SAT Reduces to Directed Hamiltonian Cycle
Claim: F is satisfiable iff G has a Hamiltonian cycle.
Proof: Þ
– Suppose 3-SAT instance has satisfying assignment x*. – Then, define Hamiltonian cycle in G as follows:
• if x*i = 1, traverse row i from left to right
• if x*i = 0, traverse row i from right to left
• for each clause Cj , there will be at least one row i in which we are going in “correct” direction to splice node Cj into tour
s
x1
x2
The University of Sydney t Page 22
x3

3-SAT Reduces to Directed Hamiltonian Cycle
Claim: F is satisfiable iff G has a Hamiltonian cycle.
Proof: Ü
– Suppose G has a Hamiltonian cycle G.
– If G enters clause node Cj , it must depart on mate edge (otherwise, some filler vertex on row i is skipped)
• thus, nodes immediately before and after Cj are connected by an edge e in G
• removing Cj from cycle, and replacing it with edge e yields HamiltoniancycleonG\{Cj }
– Continuing in this way, we are left with Hamiltonian cycle G’ in G-{C1,C2, …,Ck}.
– Set x*i = 1 iff G’ traverses row i left to right.
– Since G visits each clause node Cj , at least one of the paths is traversed
in “correct” direction, and each clause is satisfied. ▪ The University of Sydney
Page 23

Longest Path
SHORTEST-PATH: Given a digraph G = (V, E), does there exists a simple path of length at most k edges?
LONGEST-PATH: Given a digraph G = (V, E), does there exists a simple path of length at least k edges?
Theorem: 3-SAT £ P LONGEST-PATH.
Proof: Redo the proof for DIR-HAM-CYCLE, ignoring back-edge from t to s. A simple path with n edges must start from s and end at t since s only has outoing edges and t only has incoming edges.
Corollary: Deciding who wins in Catan and Ticket to Ride is NP-hard.
The University of Sydney Page 24

Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?
All 13,509 cities in US with a population of at least 500 Reference: http://www.tsp.gatech.edu
The University of Sydney
Page 25

Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?
Optimal TSP tour
Reference: http://www.tsp.gatech.edu
The University of Sydney
Page 26

Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?
11,849 holes to drill in a programmed logic array Reference: http://www.tsp.gatech.edu
The University of Sydney
Page 27

Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?
HAM-CYCLE: given a graph G = (V, E), does there exists a simple cycle that contains every node in V?
Theorem: HAM-CYCLE £ P TSP. Proof:
– Given instance G = (V, E) of HAM-CYCLE, create n cities with distance
function
– TSP instance has tour of length £ n iff G is Hamiltonian. ▪
d(u,v)=ìí1 if(u,v)ÎE î2 if(u,v)ÏE
The University of Sydney Page 29

Algorithms and hardness
Algorithmic techniques:
– Greedy
– Divide & Conquer
– Dynamic programming
– Network flow
Hardness:
– NP-hardness: Polynomial-time algorithm is unlikely Today
– How can we cope with hard problems?
The University of Sydney
Page 32

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: Polynomial-time 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 33

Cope with NP-complete problems?
The University of Sydney Page 34

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 35

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 36

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 37

Independent Set on Trees
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í 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.
– IfvÎS,we’redone.
– IfuÏSandvÏS,thenSÈ {v}isindependentÞSnotmaximum. – IF u Î S and v Ï S, then S È {v}/{u} is independent. (exchange) ▪
The University of Sydney
Page 38

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 39

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 SvÎS wv.
r
u vwx
children(u) = { v, w, x }
The University of Sydney
Page 41

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 SvÎ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 + å OPTout(v) v Î children(u)
OPTout (u) = å max {OPTin (v), OPTout (v)} v Î children(u)
The University of Sydney
Page 43

Weighted Independent Set on Trees: DP Algorithm
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] = SvÎchildren(u) Mout[v]+wv
Mout[u] = SvÎ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 44

10.1 Solving restricted instances
For example in the case when the vertex cover is small.
The University of Sydney Page 45

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 Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.
16 27
38 49
5 10
k=4
S = { 3, 6, 7, 10 }
The University of Sydney
Page 46

Vertex Cover
VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.
Vertex Cover (or Independent Set) arises naturally in many applications:
– dynamic detection of race conditions (distributed systems).
– computational biology
– Biocheimstry
– Pattern recognition
– Computer vision –…
What should we do if we need to solve it?
The University of Sydney
Page 47

Finding Small Vertex Covers
Question: What if k is small?
Brute force: O(knk+1).
– Try all nk Î 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 49

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}. Ü
– Suppose S is a vertex cover of G\{u} of size £ k-1.
– ThenSÈ{u}isavertexcoverofGofsizek. ▪
G\{u}
The University of Sydney
Page 52

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 54

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 55

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.
– There are £ 2k+1 nodes in the recursion tree; each invocation
takes O(kn) time. ▪ The University of Sydney
Page 56

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 57

Related Posts