Question? Leave a message!




Coping with NP-completeness

Coping with NP-completeness
10. EXTENDING TRACTABILITY finding small vertex covers ‣ solving NPhard problems on trees ‣ circular arc coverings ‣ vertex cover in bipartite graphs ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 PearsonAddison Wesley
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 11/3/15 5:43 AMCoping with NPcompleteness Q. Suppose I need to solve an NPcomplete problem. What should I do A. Theory says you're unlikely to find polytime algorithm. Must sacrifice one of three desired features. Solve problem to optimality. Solve problem in polynomial time. Solve arbitrary instances of the problem. This lecture. Solve some special cases of NPcomplete problems. 210. EXTENDING TRACTABILITY finding small vertex covers ‣ solving NPhard problems on trees ‣ circular arc coverings ‣ vertex cover in bipartite graphs ‣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 1 6 2 7 3 8 4 9 5 10 S = 3, 6, 7, 10 is a vertex cover of size k = 4 4Finding small vertex covers Q. VERTEXCOVER is NPcomplete. But what if k is small k+1 Brute force. O(k n ). k Try all C(n, k) = O(n ) subsets of size k. Takes O(k n) time to check whether a subset is a vertex cover. k Goal. Limit exponential dependency on k, say to O(2 k n). Ex. n = 1,000, k = 10. k+1 34 Brute. k n = 10 ⇒ infeasible. k 7 Better. 2 k n = 10 ⇒ feasible. Remark. If k is a constant, then the algorithm is polytime;
 if k is a small constant, then it's also practical. 5Finding small vertex covers Claim. 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 v and all incident edges Pf. ⇒ 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 . Pf. ⇐ Suppose S is a vertex cover of G − u of size ≤ k − 1. Then S ∪ u is a vertex cover of G. ▪ Claim. If G has a vertex cover of size k, it has ≤ k (n − 1) edges. Pf. Each vertex covers at most n − 1 edges. ▪ 6Finding small vertex covers: algorithm Claim. The following algorithm determines if G has a vertex cover of
 k size ≤ k in O(2 kn) time. VertexCover(G, k) if (G contains no edges) return true if (G contains ≥ kn edges) return false let (u, v) be any edge of G a = VertexCover(G u, k1) b = VertexCover(G v, k1) return a or b Pf. Correctness follows from previous two claims. k+1 There are ≤ 2 nodes in the recursion tree; each invocation
 takes O(kn) time. ▪ 7Finding small vertex covers: recursion tree c ifk = 0 k T(n, k)≤ cn ifk =1 ⇒ T(n, k)≤ 2 ckn 2T(n,k−1)+ckn ifk 1 ' k € k1 k1 k2 k2 k2 k2 k i 0 0 0 0 0 0 0 0 810. EXTENDING TRACTABILITY finding small vertex covers ‣ solving NPhard problems on trees ‣ circular arc coverings ‣ vertex cover in bipartite graphs ‣Independent set on trees Independent set on trees. Given a tree, find a maximum cardinality subset of nodes such that no two share an edge. Fact. A tree on at least two nodes has at least two leaf nodes. degree = 1 
 
 
 Key observation. If v is a leaf, there exists
 a maximum size independent set containing v. u v Pf. (exchange argument) Consider a max cardinality independent set S. If v ∈ S, we're done. If u ∉ S and v ∉ S, then S ∪ v is independent ⇒ S not maximum. If u ∈ S and v ∉ S, then S ∪ v − u is independent. ▪ 10Independent set on trees: greedy algorithm Theorem. The following greedy algorithm finds a maximum cardinality independent set in forests (and hence trees). IndependentSetInAForest(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. return S Pf. Correctness follows from the previous key observation. ▪ Remark. Can implement in O(n) time by considering nodes in postorder. 11Weighted independent set on trees Weighted independent set on trees. Given a tree and node weights w 0,
 v find an independent set S that maximizes Σ w . ∈ v S v Observation. If (u, v) is an edge such that v is a leaf node, then either OPT includes u or OPT includes all leaf nodes incident to u. Dynamic programming solution. Root tree at some node, say r. OPT (u) = max weight independent set
 in r of subtree rooted at u, containing u. OPT (u) = max weight independent set
 out of subtree rooted at u, not containing u. u OPT (u) = w + OPT (v) ∑ in u out v∈ children(u) v w x OPT (u) = max OPT (v), OPT (v) ∑ out in out v∈ children(u) children(u) = v, w, x 12 € Weighted independent set on trees: dynamic programming algorithm Theorem. The dynamic programming algorithm finds a maximum weighted independent set in a tree in O(n) time. can also find independent set itself (not just value) WeightedIndependentSetInATree(T) Root the tree at a node r foreach (node u of T in postorder) if (u is a leaf) ensures a node is visited M u = w in u after all its children M u = 0 out else M u = w + Σ M v ∈ in u v children(u) out M u = Σ max(M v, M v) ∈ out v children(u) in out return max(M r, M r) in out 13Context Independent set on trees. This structured special case is tractable because we can find a node that breaks the communication among the subproblems in different subtrees. u see Chapter 10.4 (but proceed with caution) Graphs of bounded tree width. Elegant generalization of trees that: Captures a rich class of graphs that arise in practice. Enables decomposition into independent pieces. 1410. EXTENDING TRACTABILITY finding small vertex covers ‣ solving NPhard problems on trees ‣ circular arc coverings ‣ vertex cover in bipartite graphs ‣Wavelengthdivision multiplexing Wavelengthdivision multiplexing (WDM). Allows m communication streams (arcs) to share a portion of a fiber optic cable, provided they are transmitted using different wavelengths. Ring topology. Special case is when network is a cycle on n nodes. Bad news. NPcomplete, even on rings. c b 1 a Brute force. Can determine if k colors
 m suffice in O(k ) time by trying all kcolorings. 4 2 Goal. O(f (k)) ⋅ poly(m, n) on rings. e f d 3 n = 4, m = 6 c, d , b, f , a, e 16Review: interval coloring Interval coloring. Greedy algorithm finds coloring such that number of colors equals depth of schedule. 
 maximum number of streams at one location 
 c d f 
 j b g i 
 a 
 e h 
 
 Circular arc coloring. Weak duality: number of colors ≥ depth. Strong duality does not hold. max depth = 2
 min colors = 3 17(Almost) transforming circular arc coloring to interval coloring Circular arc coloring. Given a set of n arcs with depth d ≤ k,
 can the arcs be colored with k colors Equivalent problem. Cut the network between nodes v and v . The arcs can 1 n be colored with k colors iff the intervals can be colored with k colors in such a way that "sliced" arcs have the same color. colors of a', b', and c' must correspond
 v 1 to colors of a", b", and c" v 0 v v 4 2 v v v v v v 0 1 4 0 2 3 v 3 18Circular arc coloring: dynamic programming algorithm Dynamic programming algorithm. Assign distinct color to each interval which begins at cut node v . 0 At each node v , some intervals may finish, and others may begin. i Enumerate all kcolorings of the intervals through v that are consistent i with the colorings of the intervals through v . i–1 The arcs are kcolorable iff some coloring of intervals ending at cut node v is consistent with original coloring of the same intervals. 0 yes c' 3 e 3 e 3 e 3 a" 3 2 2 1 1 1 1 b' 2 b' 2 2 f 2 2 f 2 2 b" 2 3 2 1 a' d 3 d 3 c" 3 c" 3 3 1 1 1 1 1 1 v v v v v v 4 0 1 2 3 0 19Circular arc coloring: running time Running time. O(k ⋅ n). The algorithm has n phases. Bottleneck in each phase is enumerating all consistent colorings. There are at most k intervals through v , so there are at most
 i k colorings to consider. Remark. This algorithm is practical for small values of k (say k = 10)
 even if the number of nodes n (or paths) is large. 2010. EXTENDING TRACTABILITY finding small vertex covers ‣ solving NPhard problems on trees ‣ circular arc coverings ‣ vertex cover in bipartite graphs ‣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 1 1' 2 2' 3 3' 4 4' 5 5' vertex cover S = 3, 4, 5, 1', 2' 22Vertex cover and matching Weak duality. Let M be a matching, and let S be a vertex cover.
 Then, M ≤ S . Pf. Each vertex can cover at most one edge in any matching. 1 1' 2 2' 3 3' 4 4' 5 5' matching M: 11', 22', 34', 45' 23Vertex cover in bipartite graphs: KönigEgerváry Theorem Theorem. KönigEgerváry In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover. 1 1' 2 2' 3 3' 4 4' 5 5' matching M: 11', 22', 34', 45' vertex cover S = 3, 4, 5, 1', 2' 24Proof of KönigEgerváry theorem Theorem. KönigEgerváry In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover. Suffices to find matching M and cover S such that M = S . Formulate max flow problem as for bipartite matching. Let M be max cardinality matching and let (A, B) be min cut. 1 ∞ 1' 1 1 2 2' 3 3' s t 4 4' 5 5' L R 25Proof of KönigEgerváry theorem Theorem. KönigEgerváry In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover. Suffices to find matching M and cover S such that M = S . Formulate max flow problem as for bipartite matching. Let M be max cardinality matching and let (A, B) be min cut. Define L = L ∩ A, L = L ∩ B , R = R ∩ A, R = R ∩ B. A B A B Claim 1. S = L ∪ R is a vertex cover. B A consider (u, v) ∈ E u ∈ L , v ∈ R impossible since infinite capacity A B thus, either u ∈ L or v ∈ R or both B A Claim 2. M = S . maxflow mincut theorem ⇒ M = cap(A, B) only edges of form (s, u) or (v, t) contribute to cap(A, B) M = cap(A, B) = L + R = S . ▪ B A 26
Website URL
Comment