CS 789 THEORY SEMINAR** **[home]

Speaker: MohammadTaghi Hajiaghayi

Affiliation: MIT

Date: February 14,
2004

Title: Fast
Algorithms For Hard Graph Problems:BiDimenationality, Minors, And (Local)
Treewidth

Abstract:

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