Lecture slides by Kevin WayneCopyright © 2005 Pearson-Addison WesleyCopyright © 2013 Kevin Waynehttp://www.cs.princeton.edu/~wayne/kleinberg-tardosLast updated on Sep 8, 2013 6:19 AM2. ALGORITHM ANALYSIS‣computational tractability‣asymptotic order of growth‣survey of common running timesSECTION 2.12. ALGORITHM ANALYSIS‣computational tractability‣asymptotic order of growth‣survey of common running times3A strikingly modern thoughtAnalytic Engine“ As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time? ” — Charles Babbage (1864)how many times do you have to turn the crank?4Brute forceBrute force. For many nontrivial problems, there is a natural brute-force search algorithm that checks every possible solution.・Typically takes 2n time or worse for inputs of size n.・Unacceptable in practice.von Neumann(1953)Gödel(1956)Edmonds(1965)Rabin(1966)Cobham(1964)Nash(1955)5Polynomial running timeDesirable scaling property. When the input size doubles, the algorithm should only slow down by some constant factor C. Def. An algorithm is poly-time if the above scaling property holds.choose C = 2d There exists constants c > 0 and d > 0 such thaton every input of size n, its running time is boundedby c nd primitive computational steps.We say that an algorithm is efficient if has a polynomial running time.Justification. It really works in practice!・In practice, the poly-time algorithms that people develop have low constants and low exponents.・Breaking through the exponential barrier of brute force typically exposes some crucial structure of the problem.Exceptions. Some poly-time algorithms do have high constantsand/or exponents, and/or are useless in practice.Q. Which would you prefer 20 n100 vs. n1 + 0.02 ln n ? 6Polynomial running timeMap graphs in polynomial timeMikkel ThorupDepartment of Computer Science, University of CopenhagenUniversitetsparken 1, DK-2100 Copenhagen East, [email protected], Grigni, and Papadimitriou (WADS’97and STOC’98)have introduced a modified notion of planarity, where twofaces are considered adjacent if they share at least one point.The corresponding abstract graphs are called map graphs.Chen et.al. raised the question of whether map graphs can berecognized in polynomial time. They showed that the decisionproblem is in NP and presented a polynomial time algorithmfor the special case where we allow at most 4 faces to intersectin any point — if only 3 are allowed to intersect in a point, weget the usual planar graphs.Chen et.al. conjectured that map graphs can be recognizedin polynomial time, and in this paper, their conjectureis settledaffirmatively.1. IntroductionRecently Chen, Grigni, and Papadimitriou [4, 5] suggestedthe study of a modified notion of planarity. The basic frame-work is the same as that of planar graphs. We are given a set ofnon-overlapping faces in the plane, each being a disc homeo-morphism. By non-overlapping,wemeanthattwofacesmayonly intersect in their boundaries. The plane may or may notbe completely covered by the faces. A traditional planar graphis obtained as follows. The vertices are the faces, and twofaces are neighbors if their intersection contains a non-trivialcurve. Chen et.al. [4, 5] suggested simplifying the definition,by saying that two faces are neighbors if and only if they in-tersect in at least one point. They called the resulting graphs“planar map graphs”. Here we will just call them map graphs.Note that there are non-planar map graphs, for as illustratedin Figure 1, map graphs can contain arbitrarily large cliques.We sha ll refer to the first type of clique as a flowerwith thepetals intersecting in a center.Thesecondisahamantashbased on three distinct corner points.Eachofthethreepairsof corner points is connected by a side of parallel faces.InMost of this work was done while the author visited MIT.Chen et.al. called flowers for pizzas, but “flower” seems more natural.Figure 1. Large cliques in mapsaddition, the hamantach may have at most two triangle facestouching all three corners. In [5] there is a classification ofall the different types of large cliques in maps. Chen et.al. [5]showed that recognizing map graphs is in NP, hence that therecognition can be done in singly exponential time. However,they conjectured that, in fact, map graphs can be recognized inpolynomial time. They supported their conjecture by showingthat if we allow at most 4 faces to meet in any single point, theresulting map graphs can be recognized in polynomial time. Inthis paper, we settle the general conjecture, showing that givenagraph,wecandecideinpolynomialtimeifitisamapgraph.The algorithm can easily be modified to draw a correspondingmap if it exists.Map coloring It should be noted that coloring of map graphsdates back to Ore and Plummer in 1969 [8], that is, they wantedto color the faces so that any two intersecting faces got differentcolors. For an account of colorful history, the reader is referredto [7,2.5]. In particular, the history provides an answer to aproblem of Chen et.al. [5]: if at most 4 faces meet in any singlepoint, can we color the map with 6 colors? It is straightforwardto se e that the resulting graphs are 1-planar, meaning that theycan be drawn in the plane s uch that each edge is crossed by atmost one other edge. Already in 1965, Ringel [9] conjecturedthat all 1-planar graphs can be colored with 6 colors, and thisconjecture was settled in 1984 by Borodin [2], so the answerto Chen et.al.’s problem is: yes.Map metrics The shortest path metrics of map graphs arecommonly used in prizing systems, where you pay for cross-Map graphs in polynomial timeMikkel ThorupDepartment of Computer Science, University of CopenhagenUniversitetsparken 1, DK-2100 Copenhagen East, [email protected], Grigni, and Papadimitriou (WADS’97and STOC’98)have introduced a modified notion of planarity, where twofaces are considered adjacent if they share at least one point.The corresponding abstract graphs are called map graphs.Chen et.al. raised the question of whether map graphs can berecognized in polynomial time. They showed that the decisionproblem is in NP and presented a polynomial time algorithmfor the special case where we allow at most 4 faces to
View Full Document
Unlocking...