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”, in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 3–15.

BibTeX

@InProceedings{GridWagner_ISAAC2006,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Ken-ichi Kawarabayashi},
  TITLE         = {Algorithmic Graph Minor Theory: Improved Grid Minor Bounds
                   and {Wagner}'s Contraction},
  BOOKTITLE     = {Proceedings of the 17th Annual International Symposium on
                   Algorithms and Computation (ISAAC 2006)},
  bookurl       = {http://www.isical.ac.in/~isaac06},
  VOLUME        = 4288,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  ADDRESS       = {Calcutta, India},
  MONTH         = {December 18--20},
  YEAR          = 2006,
  PAGES         = {3--15},

  papers        = {GridWagner_Algorithmica},
  copyright     = {The paper is \copyright Springer-Verlag.},
  award         = {Awarded Best Paper.
                   Invited to special issue of \emph{Algorithmica}.},
  doi           = {https://dx.doi.org/10.1007/11940128_3},
  dblp          = {https://dblp.org/rec/conf/isaac/DemaineHK06},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/11940128_3">SpringerLink</A>.},
}

Abstract:

We explore the three main avenues of research still unsolved in the algorithmic graph-minor theory literature, 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. 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 (379k), gzipped PostScript (160k), and PDF (221k).

See information on file formats.

[Google Scholar search]

Related papers:

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