**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”, in*Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)*, New Orleans, Louisiana, January 11–13, 2004, pages 823–832. **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, 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 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 & Seymour's graph-minors work. We believe this approach opens the way to further development for problems on*H*-minor-free graphs. **Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (236k), gzipped PostScript (87k), and PDF (221k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- HMinorFree_JACM (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.