We improve the running time of the general algorithmic technique known as Baker's approach (1994) on H-minor-free graphs from O(n f (|H|) ) to O(f (|H|)n O(1) ) showing that it is fixed-parameter tractable w.r.t. the parameter |H|. The numerous applications include e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements. On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010) and a Bakerstyle decomposition into 2 graphs of bounded treewidth. We use these algorithms to derive faster 2-approximations; furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique. We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. We provide a uniform algorithm running in time where n is the size of the input and k is the number of vertices or edges in the solution. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes, many of which were previously not even known to admit an algorithm with running time better than O(2 k n O(1) ). We obtain as a corollary that all problems with a minormonotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality. Keywords: Parameterized Complexity; Graph Minors; Odd Minors; Subexponential Algorithms; Kernels. One of the most seminal results in algorithmic graph theory is arguably Baker's approach [1] for designing polynomialtime approximation schemes (PTAS) for a wide range of problems on planar graphs. Ever since its discovery, it has been applied and generalized in various ways, see e.g. [2, 3, 4, 5, 6, 7, 8, 9] . The essence of the idea is the following: for any given t, one can partition a planar graph into t parts, so that removing any one of the parts results in a graph of bounded treewidth. Now, to obtain a PTAS, we observe that if t is appropriately chosen, there must exist a part that contains at most an ǫ-fraction of an optimal solution; this can often be combined with the solution in the remainder of the graph to obtain a (1 + ǫ)-approximation. H-minor-free graphs, i.e. proper graph classes that are closed under building minors, have gained significant attention in the past two decades, especially due to Robertson and Seymour's graph minor theory, one of the deepest and most far-reaching theories in discrete mathematics in the past few decades. These classes include, e.g. planar graphs, bounded-genus graphs, linklessly embeddable graphs and apex graphs. Using the deep Robertson-Seymour (RS-) decomposition theorem [10], Grohe [4] generalized Baker's technique to H-minor-free graphs and Demaine et al. [7] showed the partitioning theorem mentioned above for all these graph classes. However, both their methods result in algorithms with running time O(n f (|H|) ), for some computable function f ; since H is assumed to be fixed, this is considered polynomial. Improving Baker's Decomposition. We provide the first algorithm for Baker's decomposition running in time O(g(|H|)n O(1) ), for some computable function g. This is a significant acceleration of the previous results, especially considering the fact that the constants in graph minor theory, such as the functions f, g above, are usually huge. This immediately implies similar improvements on all the consequences of this algorithm, especially all the generic approximation algorithms and schemes in [4, 7] and Baker's original problems [1] . In particular, we obtain the first 2-approximation for COLORING H-minor-free graphs in the given time bound and the first PTAS for INDEPENDENT SET, MINIMUM COLOR SUM, MAX-CUT, MAXIMUM P -MATCHING, and DOMINATING SET on these graph classes while avoiding |H| in the exponent of n in their running time. Our main idea is derived from Dawar et al.'s approach [11] of finding a certain tree decomposition of H-minor-free graphs that is more tractable than the RS-decomposition. Parameterized Complexity. In the language of parameterized complexity, our result above shows that partitioning H-minor-free graphs in the described way is fixed-parameter tractable (FPT) when parameterized by |H|. In this framework, for a given problem of size n and parameter k, we are interested in algorithms with a running time of O(f (k)n O(1) ), where f is some computable function depending solely on k; we then say that the problem at hand is in FPT. The theory also provides negative evidence that some problems are most likely not FPT; we refer to the books of Downey and Fellows [12] and Flum and Grohe [13] for more background on parameterized complexity. Once a problem is shown to be FPT, the challenge is to provide algorithms that have the smallest dependence on the parameter k, i.e. make the function f in the running time as small as possible. It is especially desirable to obtain subexponential functions and thus provide particularly fast algorithms. Whereas this is often not possible in general graphs, a plethora of results exist that show the existence of such algorithms on restricted graph classes, such as H-minor-free graphs. Perhaps the most general technique to obtain subexponential parameterized algorithms on these graph classes is the theory of bidimensionality [14] that captures almost all known results of this type on H-minor-free graphs. Still, this theory does not apply to a number of prominent problems, such as STEINER TREE, CONNECTED DOMINATING SET, and DIRECTED k-PATH. One way to show fixed-parameter tractability of a problem is to show the existence of a kernel for the problem, which is a polynomial-time algorithm that transforms any instance into an equivalent instance whose size is bounded by a function g solely dependent on k, called the size of the kernel. Kernelization can be seen as polynomial-time pre-processing with a quality guarantee and has gained much theoretical importance in the recent years -besides its natural practical importance. For an introduction to kernels we refer to the survey by Guo and Niedermeier [15] . In this work, we provide a new framework, that we call guess and conquer, to obtain (nearly) subexponential parameterized algorithms on H-minor-free graphs for an abundant number of parameterized problems. Whenever the problem at hand admits a minor-monotone subexponential kernel, our method results indeed in a subexponential algorithm; otherwise, we obtain an algorithm with a running time O(2
The question of the existence of a subexponential-time algorithm for PLANAR STEINER TREE was first explicitly pursued by Tazari REF .
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
ArXiv
ArXiv
Mathematics Computer Science