Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction”, Algorithmica, volume 54, number 2, June 2009, pages 142–180. Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006.

BibTeX

@Article{GridWagner_Algorithmica,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Ken-ichi Kawarabayashi},
  TITLE         = {Algorithmic Graph Minor Theory: Improved Grid Minor Bounds
                   and {Wagner}'s Contraction},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 54,
  NUMBER        = 2,
  MONTH         = {June},
  YEAR          = 2009,
  PAGES         = {142--180},
  NOTE          = {Special issue of selected papers from the 17th Annual
                   International Symposium on Algorithms and Computation, 2006.},
  doi           = {https://dx.doi.org/10.1007/s00453-007-9138-y},
  dblp          = {https://dblp.org/rec/journals/algorithmica/DemaineHK09},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00453-007-9138-y">SpringerLink</A>.},
  papers        = {GridWagner_ISAAC2006},
  copyright     = {The paper is \copyright Springer-Verlag.},
}

Abstract:

We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties.

First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely, K_3, k-minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner's Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Availability:

The paper is available in PostScript (846k) and PDF (462k).

See information on file formats.

[Google Scholar search]

Related papers:

GridWagner_ISAAC2006 (Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction)