Paper by Erik D. Demaine

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.

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, K3,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.

This paper is also available from SpringerLink.

The paper is \copyright Springer-Verlag.

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)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 23, 2024 by Erik Demaine.