Designing Subexponential Algorithms: Problems, Techniques & Structures
MetadataVis full innførsel
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 2O(√n) and parameterized algorithms with running time 2O(√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 as Vertex 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.