Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs”, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 329–344.

Abstract:

We prove two structural decomposition theorems about graphs excluding a fixed odd minor H, and show how these theorems can be used to obtain approximation algorithms for several algorithmic problems in such graphs. Our decomposition results provide new structural insights into odd-H-minor-free graphs, on the one hand generalizing the central structural result from Graph Minor Theory, and on the other hand providing an algorithmic decomposition into two bounded-treewidth graphs, generalizing a similar result for minors. As one example of how these structural results conquer difficult problems, we obtain a polynomial-time 2-approximation for vertex coloring in odd-H-minor-free graphs, improving on the previous O(|V(H)|)-approximation for such graphs and generalizing the previous 2-approximation for H-minor-free graphs. The class of odd-H-minor-free graphs is a vast generalization of the well-studied H-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-H-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of H-minor-free graphs, permitting a quadratic number of edges.

Availability:

The paper is available in PostScript (405k), gzipped PostScript (141k), and PDF (288k).

See information on file formats.

[Google Scholar search]