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, disk dimension, 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/or 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 and 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 and Seymour's graph-minors work.
We believe this approach opens the way to further development on problems in
H-minor-free graphs.