TY - CONF
T1 - Algorithmic graph minor theory: Decomposition, approximation, and coloring
T2 - Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Y1 - 2005
A1 - Demaine,E. D
A1 - Hajiaghayi, Mohammad T.
A1 - Kawarabayashi,K.
KW - algorithmic graph minor theory
KW - approximation algorithm
KW - combinatorial polylogarithmic approximation
KW - computational complexity
KW - constant-factor approximation
KW - graph algorithm
KW - graph coloring
KW - graph colouring
KW - half-integral multicommodity flow
KW - largest grid minor
KW - maximization problem
KW - minimization problem
KW - polynomial-time algorithm
KW - subexponential fixed-parameter algorithm
KW - topological graph theory
KW - treewidth
AB - At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.
JA - Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
M3 - 10.1109/SFCS.2005.14
ER -