**Reference**:- Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Subexponential parameterized algorithms on graphs of bounded-genus and
*H*-minor-free graphs”,*Journal of the ACM*, volume 52, number 6, 2005, pages 866–893. **Abstract**:-
We introduce a new framework for designing fixed-parameter algorithms
with subexponential running
time—2
^{O(√k)}*n*^{O(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 2^{O(√k)}*n*^{h}, where*h*is a constant depending only on*H*, which is polynomial for*k*=*O*(log^{2}*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. **Comments**:- This paper is also available from the ACM Digital Library.
**Length**:- The paper is 26 pages.
**Availability**:- The paper is available in PostScript (694k), gzipped PostScript (276k), and PDF (409k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- HMinorFree_SODA2004 (Subexponential parameterized algorithms on graphs of bounded-genus and
*H*-minor-free graphs)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.