Designing Subexponential Algorithms: Problems, Techniques & Structures
Frederic Dorn · 2007
In this thesis we focus on subexponential algorithms for NP-hard graph problems: exact and parameterized algorithms that have a truly subexponential running time behavior. For input instances of size n we study exact algorithms with running time 2 √ n) and parameterized algorithms with running time 2 √ k) ·nO(1) with parameter k, respectively. We study a class of problems for which we design such algorithms for three different types of graph classes: planar graphs, graphs of bounded genus, and H-minor-free graphs. We distinguish between unconnected and connected problems, and discuss how to conceive parameterized and exact algorithms for such problems. We improve upon existing dynamic programming techniques used in algorithms solving those problems. We compare tree-decomposition and branch-decomposition based dynamic programming algorithms and show how to unify both algorithms to one single algorithm. Then we give a dynamic programming technique that reduces much of the computation involved to fast matrix multiplication. In this manner, we obtain branch-decomposition based algorithms on numerous problems, such asVertex Cover and Dominating Set. We also show how to exploit planarity for obtaining faster dynamic programming approaches, a) in connection with fast matrix multiplication and b) for tree-decompositions. Furthermore, we focus on connected problems in particular, and their relation to the input graph structure. We state the basis for how the latter problems can be attacked for graph classes that inherit the Catalan structure. Truly subexponential algorithms for edge-subset problems such as k-Longest Path and Planar Graph TSP are derived by employing the planar graph structure. Moreover, we investigate how to obtain truly subexponential algorithms for torus-embedded graphs, bounded genus graph and Hminor-free graphs, by first using planarization techniques, and then proving the Catalan structure for the planarized instances. Preface “So Long, and Thanks for All the Fish” All work on this thesis has been funded mainly by Exact Algorithms for Hard Problems NFR FRINAT grant and additionally by the L. Meltzer Hoyskolefond. My first and sincere thanks go to my supervisor Professor Fedor Fomin for his wise guidance. Without his foresight, patience and trust in me, I might not have come to this point. Further, I send my warmest thanks to all the members (and former members) of the algorithms group in Bergen (in alphabetical order), with whom I was sharing a great and inspiring working atmosphere: Joanna Bauer, Lene Favrholdt, Serge Gaspers, Petr Golovach, Pinar Heggernes, Kjartan Hoie, Daniel Lokshtanov, Federico Mancini, Fredrik Manne, Daniel Meister, Rodica Mihai, Morten Mjelde, Charis Papadopoulos, Artem Pyatkin, Saket Saurabh, Christian Sloper, Alexey Stepanov, Jan Arne Telle, Yngve Villanger, and Qin Xin. Many thanks for the research invitations and hospitality of Hans Bodlaender, Andrzej Lingas, Bojan Mohar, Ulrike Stege, and Dimitrios Thilikos. I also take the opportunity to warmly thank Hans Bodlaender, Eelko Penninkx, Jan Arne Telle, and Dimitrios Thilikos for collaborating on the results of this thesis and Jochen Alber, Matt DeVos, Eva-Marta Lundell, Bojan Mohar, Rolf Niedermeier, and Ulrike Stege for other collaborations. Also, I want to thank the European Association for Theoretical Computer Science (EATCS) for giving me the honor of receiving their award. Last but not least, I want to thank all my friends, present and past, for all your love and support through hard and good times. This work is dedicated to my sister Nathalie Dorn, who has always been my greatest support—danke! The thesis is based on the results of the following works: • F. Dorn, Dynamic programming and fast matrix multiplication, in Proceedings of the fourteenth Annual European Symposium on Algorithms (ESA 2006), vol. 4168 of LNCS, Springer, 2006, pp. 280–291. • F. Dorn, How to use planarity efficiently: new tree-decomposition based algorithms, in Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), LNCS, Springer, 2007, p. to appear. • F. Dorn, F. V. Fomin, and D. M. Thilikos, Fast subexponential algorithm for non-local problems on graphs of bounded genus, in Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), vol. 4059 of LNCS, Springer, 2006, pp. 172–183. • F. Dorn, F. V. Fomin, and D. M. Thilikos, Catalan structures and dynamic programming on H-minor-free graphs, submitted, (2007). • F. Dorn, F. V. Fomin, and D. M. Thilikos, Subexponential parameterized algorithms, in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), vol. 4596 of LNCS, Springer, 2007, pp.15–27. • F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Fomin, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, submitted (2006). • F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Fomin, Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, in Proceedings of the thirteenth Annual European Symposium on Algorithms (ESA 2005), vol. 3669 of LNCS, Springer, 2005, pp. 95–106. • F. Dorn and J. A. Telle, Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm, submitted, (2005). • F. Dorn and J. A. Telle, Two birds with one stone: the best of branchwidth and treewidth with one algorithm, in Proceedings of the seventh Latin American Theoretical Informatics Symposium (LATIN’06), vol. 3887 of LNCS, Springer, 2006, pp. 386–397. This work includes only results to which I contributed in significant manner and to whose achievement I played a major role. Bergen, 19.7.07 Frederic Dorn