Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{HMinorFree_SODA2004,
  AUTHOR        = {Erik D. Demaine and Fedor V. Fomin and
                   MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos},
  TITLE         = {Subexponential parameterized algorithms on graphs of
                   bounded-genus and $H$-minor-free graphs},
  BOOKTITLE     = {Proceedings of the 15th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2004)},
  bookurl       = {http://www.siam.org/meetings/da04/},
  ADDRESS       = {New Orleans, Louisiana},
  MONTH         = {January 11--13},
  YEAR          = 2004,
  PAGES         = {823--832},

  length        = {10 pages},
  withstudent   = 1,
  ee            = {http://dl.acm.org/citation.cfm?id=982792.982918},
  papers        = {HMinorFree_JACM},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineFHT04},
}

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² 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 bounded-genus graphs and H-minor-free graphs)