FAST ALGORITHMS FOR HARD GRAPH PROBLEMS:
BIDIMENSIONALITY, MINORS, AND (LOCAL) TREEWIDTH


MohammadTaghi Hajiaghayi, CSAIL, MIT

Our newly developing theory of bidimensional graph problems provides
general techniques for designing efficient fixed-parameter algorithms
and approximation algorithms for NP-hard graph problems in broad
classes of graphs. This theory applies to graph problems that are
\emph{bidimensional} in the sense that (1) the solution value for the
$k \times k$ grid graph (and similar graphs) grows with $k$, typically
as $\Omega(k^2)$, and (2) the solution value goes down when
contracting edges and optionally when deleting edges. Examples of such
problems include feedback vertex set, vertex cover, minimum maximal
matching, face cover, a series of vertex-removal parameters,
dominating set, edge dominating set, $r$-dominating set, connected
dominating set, connected edge dominating set, connected
$r$-dominating set, and unweighted TSP tour (a walk in the graph
visiting all vertices).  Bidimensional problems have many structural
properties; for example, any graph embeddable in a surface of bounded
genus has treewidth bounded above by the square root of the problem's
solution value. These properties lead to efficient---often
subexponential---fixed-parameter algorithms, as well as
polynomial-time approximation schemes, for many minor-closed graph
classes. One type of minor-closed graph class of particular relevance
has bounded local treewidth, in the sense that the treewidth of a
graph is bounded above in terms of the diameter; indeed, we show that
such a bound is always at most linear. The bidimensionality theory
unifies and improves several previous results. The theory is based on
algorithmic and combinatorial extensions to parts of the
Robertson-Seymour Graph Minor Theory, in particular initiating a
parallel theory of graph contractions. The foundation of this work is
the topological theory of drawings of graphs on surfaces.

This is from several joint papers mainly with Erik D. Demaine
**********************************************************************