Decomposition, approximation, and coloring of odd-minor-free graphs
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 g...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery / Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62025 https://orcid.org/0000-0003-3803-5703 |
| Summary: | 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(jV (H)j)-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. |
|---|