Exact exponential algorithms

exponential running time algorithms and exponential time algorithms structures measures and bounds
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Nov 24, 2014, 8:24 AMCoping with NP-completeness Q. Suppose I need to solve an NP-hard problem. What should I do? A. Sacrifice one of three desired features. i. Solve arbitrary instances of the problem. ii. Solve problem to optimality. iii. Solve problem in polynomial time. Coping strategies. i. Design algorithms for special cases of the problem. ii. Design approximation algorithms or heuristics. iii. Design algorithms that may take exponential time. 2INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 10.2Independent set on trees Independent set on trees. Given a tree, find a maximum cardinality subset of nodes such that no two are adjacent. Fact. A tree has at least one node that is a leaf (degree = 1). Key observation. If node v is a leaf, there exists a max cardinality independent set containing v. u Pf. exchange argument v Consider a max cardinality independent set S. If v ∈ S, we're done. Let (u, v) be some edge. 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 ▪ 4Independent set on trees: greedy algorithm Theorem. The following greedy algorithm finds a max cardinality independent set in forests (and hence trees). Pf. Correctness follows from the previous key observation. ▪ INDEPENDENT-SET-IN-A-FOREST (F) _____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ S ← ∅. WHILE (F has at least 1 edge) e ← (u, v) such that v is a leaf. S ← S ∪ v . delete u and v and all incident edges F ← F – u, v . RETURN S ∪ nodes remaining in F . _____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ Remark. Can implement in O(n) time by considering nodes in postorder. 5Weighted 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 Dynamic programming solution. Root tree at some node, say r. OPT (u) = max weight independent set of subtree rooted at u, in containing u. OPT (u) = max weight independent set of subtree rooted at u, out not containing u. r OPT = max OPT (r), OPT (r) . in out OPT (u) = w + OPT (v) OPT (u) = w + ∑ OPT (v) ∑ in u out in u out v∈ children(u) v∈ children(u) u OPT (u) = max OPT (v), OPT (v) OPT (u) = ∑ max OPT (v), OPT (v) ∑ out in out out in out v w x v∈ children(u) v∈ children(u) children(u) = v, w, x € € 6Weighted independent set on trees: dynamic programming algorithm Theorem. The dynamic programming algorithm finds a max weighted independent set in a tree in O(n) time. can also find independent set itself (not just value) WEIGHTED-INDEPENDENT-SET-IN-A-TREE (T) _____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ Root the tree T at a node r. S ← ∅. 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 _____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 7NP-hard problems on trees: context Independent set on trees. Tractable because we can find a node that breaks the communication among the subproblems in different subtrees. u Linear-time on trees. VERTEX-COVER, DOMINATING-SET, GRAPH-ISOMORPHISM, ... 8INTRACTABILITY III special cases: trees ‣ special cases: planarity ‣ approximation algorithms ‣ exact exponential algorithms ‣ SECTION 23.1Planarity Def. A graph is planar if it can be embedded in the plane in such a way that no two edges cross. K is nonplanar K is nonplanar 5 3,3 planar Applications. VLSI circuit design, computer graphics, ... 10Planarity testing Theorem. Hopcroft-Tarjan 1974 There exists an O(n) time algorithm to determine whether a graph is planar. simple planar graph has at ≤ 3n edges Efficient Planarity Testing JOHN HOPCROFT AND ROBERT TAR JAN Cornell University, Ithaca, New York ABSTRACT. This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm uses depth-first search and has O(V) time and space bounds, where V is the number of vertices in G. An ALGOS implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds. KEY WORDS AND PHRASES: algorithm, complexity, depth-first search, embedding, genus, graph, palm tree, planarity, spanning tree CR CATEGORIES: 3.24, 5.25, 5.32 1. Introduction Graph theory is an endless source of easily stated yet very hard problems. Many of these problems require algorithms; given a graph, one may ask if the graph has a certain prop- erty, and an algorithm is to provide the answer. Since graphs are widely used as models of real phenomena, it is important to discover ecient algorithms for answering graph- theoretic questions. This paper presents an efficient algorithm to determine whether a graph G can be embedded (without any crossing edges) in the plane. 11 The planarity algorithm may be viewed as an iterative version of a recursive method originally proposed by Auslander and Patter 1 and correctly formulated by Goldstein 2. The algorithm uses depth-first search to order the calculations and thereby achieve efficiency. Depth-first search, or backtracking, has been widely used for finding solu- tions to problems in combinatorial theory and artificial intelligence 3, 4. Recently this type of search has been used to construct efficient algorithms for solving several problems in graph theory, including finding biconnected components 5, 6, finding triconnected components 7, 81, finding strongly connected components 61, finding dominators 9, and determining whether a directed graph is reducible 10, 11. In order to analyze the theoretical efficiency of the planarity algorithm, a random ac- cess computer model is used. Data storage and retrieval, arithmetic operations, compari- sons, and logical operations are assumed to require fixed times. A memory cell is allowed to hold integers whose absolute value is bounded by kV for some constant k, where V is the number of vertices in the problem graph. Cook 12 describes an exact computer model along these lines. If f and g are functions of x, we say "f(x) is O(g(x))" if, for some constants kI and k2, If(x) I - ki I g(x) I + k2 for all x. Within this framework, the planarity algorithm has 0 (V) time and space bounds and is optimal to within a constant factor. The practical efficiency of the algorithm was measured by implementing it in ALGOL Copyright () 1974, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This research was supported by the Hertz Foundation, the NSF, and the Office of Naval Research under grants N-0O014-A-Ol12-0057 and N-00014-67-A-0077-0021. Authors' present addresses: J. Hopcroft, Department of Computer Science, Cornell University, Ithaca, NY 14850; R. Tarjan, Department of Electrical Engineering, University of California, Berkeley, CA 94720. Journal of the Association for Computing Machinery, Vol. 21, No. 4, October 1974, pp. 549-568. Polynomial time detour Graph minor theorem. Robertson-Seymour 1980s Pf of theorem. Tour de force. 3 Corollary. There exist an O(n ) algorithm to determine if a graph can be embedded in the torus in such a way that no two edges cross. more than 2↑2↑2↑(n/2) Mind boggling fact 1. The proof is highly nonconstructive Mind boggling fact 2. The constant of proportionality is enormous “ Unfortunately, for any instance G = (V, E) that one could fit into the known 70 universe, one would easily prefer n to even constant time, if that constant had to be one of Robertson and Seymour's. ” — David Johnson Theorem. There exists an explicit O(n) algorithm. 3 Practice. LEDA implementation guarantees O(n ). 12Problems on planar graphs Fact 0. Many graph problems can be solved faster in planar graphs. Ex. Shortest paths, max flow, MST, matchings, … Fact 1. Some NP-complete problems become tractable in planar graphs. Ex. MAX-CUT, ISING, CLIQUE, GRAPH-ISOMORPHISM, 4-COLOR, ... Fact 2. Other NP-complete problems become easier in planar graphs. Ex. INDEPENDENT-SET, VERTEX-COVER, TSP, STEINER-TREE, ... An O(nlogn)AlgorithmforMaximum st-Flow inaDirectedPlanarGraph GLENCORABORRADAILEANDPHILIPKLEIN Brown University, Providence, Rhode Island Abstract. Wegivethefirstcorrect O(nlogn)algorithmforfindingamaximumst-flowinadirected planargraph.Afterapreprocessingstepthatconsistsinfindingsingle-sourceshortest-pathdistances inthedual,thealgorithmconsistsofrepeatedlysaturatingtheleftmostresidual s-to-t path. Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: NonnumericalAlgorithmsandProblems GeneralTerms:Algorithms AdditionalKeyWordsandPhrases:Maximumflow,planargraphs ACMReferenceFormat: Borradaile, G. and Klein, P. 2009. An O(nlogn) algorithm for maximum st-flow in a directed 13 planar graph. J. ACM 56, 2, Article 9 (April 2009), 30 pages. DOI = 10.1145/1502793.1502798 http://doi.acm.org/10.1145/1502793.1502798 9 1. Introduction Informally,themaximumst-flowproblemisasfollows:givenagraphwithpositive arc-capacities,andgivenasourcevertex s andasinkvertex t,thegoalistofinda waytoroutethemaximumamountofasinglecommodityalongs-to-t pathsinsuch awaythattheamountofcommoditypassingthroughanarcisatmostthecapacity of the arc. In the minimum st-cut problem, the goal is to find a minimum-capacity set of arcs such that each s-to-t path includes at least one arc in the set. Formal definitionswillbegiveninSection4.5. The history of maximum-flow and minimum-cut problems Schrijver 2002 is tied closely to planar graphs. During the height of the cold war, the United States A preliminary version of this article was published in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06),ACM,NewYork,2006,pp.524–533. G.BorradailewassupportedbyNSERCPGS-D,Rowland-LloydCST,Kanellakis,aBrownUniversity DissertationFellowship,andNSFGrantCCF-0635089.P.KleinwassupportedbyNSFGrantCCF- 0635089. Authors’ addresses: Department of Computer Science, Brown University, Providence, RI 02912, e-mail:glencora;kleincs.brown.edu. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantageandthatcopiesshowthisnoticeonthefirstpageorinitialscreenofadisplayalongwiththe full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstractingwithcreditispermitted.Tocopyotherwise,torepublish,topostonservers,toredistribute tolists,ortouseanycomponentofthisworkinotherworksrequirespriorspecificpermissionand/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, NewYork,NY10121-0701USA,fax+1(212)869-0481,orpermissionsacm.org. ⃝ C 2009ACM0004-5411/2009/04-ART95.00 DOI10.1145/1502793.1502798 http://doi.acm.org/10.1145/1502793.1502798 JournaloftheACM,Vol.56,No.2,Article9,Publicationdate:April2009.Planar graph 3-colorability PLANAR-3-COLOR. Given a planar graph, can it be colored using 3 colors so that no two adjacent nodes have the same color? 14Planar map 3-colorability PLANAR-MAP-3-COLOR. Given a planar map, can it be colored using 3 colors so that no two adjacent regions have the same color? yes instance 15Planar map 3-colorability PLANAR-MAP-3-COLOR. Given a planar map, can it be colored using 3 colors so that no two adjacent regions have the same color? no instance 16Planar graph and map 3-colorability reduce to one another Theorem. PLANAR-3-COLOR ≣ PLANAR-MAP-3-COLOR. P Pf sketch. Nodes correspond to regions. Two nodes are adjacent iff they share a nontrivial border. e.g., not Arizona and Colorado 17Planar 3-colorability is NP-complete Theorem. PLANAR-3-COLOR ∈ NP-complete. Pf. Easy to see that PLANAR-3-COLOR ∈ NP. We show 3-COLOR ≤ PLANAR-3-COLOR. P Given 3-COLOR instance G, we construct an instance of PLANAR-3-COLOR that is 3-colorable iff G is 3-colorable. 18Planar 3-colorability is NP-complete Lemma. W is a planar graph such that: In any 3-coloring of W, opposite corners have the same color. Any assignment of colors to the corners in which opposite corners have the same color extends to a 3-coloring of W. planar gadget W 19Planar 3-colorability is NP-complete Lemma. W is a planar graph such that: In any 3-coloring of W, opposite corners have the same color. Any assignment of colors to the corners in which opposite corners have the same color extends to a 3-coloring of W. Pf. The only 3-colorings (modulo permutations) of W are shown below. ▪ planar gadget W 20