We introduce a new framework for designing fixed-parameter algorithms with
subexponential running
time—2O(√k) nO(1).
Our results apply to a broad family of graph problems, called bidimensional
problems, which includes many domination and covering problems such as
vertex cover, feedback vertex set, minimum maximal matching, dominating set,
edge dominating set, clique-transversal set, and many others restricted to
bounded-genus graphs. Furthermore, it is fairly straightforward to prove that
a problem is bidimensional. In particular, our framework includes as special
cases all previously known problems to have such subexponential algorithms.
Previously, these algorithms applied to planar graphs,
single-crossing-minor-free graphs, and map graphs; we extend these results to
apply to bounded-genus graphs as well. In a parallel development of
combinatorial results, we establish an upper bound on the treewidth (or
branchwidth) of a bounded-genus graph that excludes some planar graph H
as a minor. This bound depends linearly on the size |V(H)| of the
excluded graph H and the genus g(G) of the
graph G, and applies and extends the graph-minors work of Robertson
& Seymour.
Building on these results, we develop subexponential fixed-parameter algorithms
for dominating set, vertex cover, and set cover in any class of graphs
excluding a fixed graph H as a minor. In particular, this general
category of graphs includes planar graphs, bounded-genus graphs,
single-crossing-minor-free graphs, and any class of graphs that is closed under
taking minors. Specifically, the running time is
2O(√k) nh,
where h is a constant depending only on H, which is polynomial
for k = O(log2 n). We introduce a
general approach for developing algorithms on H-minor-free graphs, based
on structural results about H-minor-free graphs at the heart of
Robertson & Seymour's graph-minors work. We believe this approach opens the
way to further development for problems on H-minor-free graphs.