 MohammadTaghi Hajiaghayi, MIT, USA School of Computer Science & School of Mathematics
Abstract
Our newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixedparameter algorithms and approximation algorithms for NPhard graph problems in broad classes of graphs. This theory applies to graph problems that are bidimensional in the sense that (1) the solution value for the k * k grid graph (and similar graphs) grows with k, typically as Ω(k2), 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 vertexremoval parameters, dominating set, edge dominating set, rdominating set, connected dominating set, connected edge dominating set, connected rdominating 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 efficientoften subexponentialfixedparameter algorithms, as well as polynomialtime approximation schemes, for many minorclosed graph classes. One type of minorclosed 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 various results. The theory is based on algorithmic and combinatorial extensions to parts of the RobertsonSeymour 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. It is worth mentioning that before this talk, there is a threehours tutorial which introduces in more details the concepts used in this talk such as fixed parameter algorithms, treewidth and graph minors.
 Schedule
Title  Time 
Fixed Parameter Algorithms  9:0010:15 
Treewidth and Graph Minors  10:4512:00 
Fast Algorithms for Hard Graph Problems Bidimensionality, Minors and (local) Treewidth  14:0016:00 

Date: Thursday, Sep. 8, 2005 
Place: Lecture Hall, Niavaran Bldg., Niavaran Sqr., IPM, Tehran, Iran 
 
