
Research
Abstracts  2007 
Bidimensionality TheoryErik D. Demaine & MohammadTaghi HajiaghayiOverviewThe theory of bidimensionality provides general techniques for designing efficient fixedparameter algorithms and approximation algorithms for a broad range of NPhard graph problems in a broad range 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 Ω(k^{2}), and (2) the solution value goes down when contracting edges and optionally when deleting edges in the graph. Many problems are bidimensional; a few classic examples are vertex cover, dominating set, and feedback vertex set. Graph classesResults about bidimensional problems have been developed for increasingly general families of graphs, all generalizing planar graphs. The first two classes of graphs relate to embeddings on surfaces. A graph is planar if it can be drawn in the plane (or the sphere) without crossings. A graph has (Euler) genus at most g if it can be drawn in a surface of Euler characteristic g. A class of graphs has bounded genus if every graph in the class has genus at most g for a fixed g. The next three classes of graphs relate to excluding minors. Given an edge e = {v,w} in a graph G, the contraction of e in G is the result of identifying vertices v and w in G and removing all loops and duplicate edges. A graph H obtained by a sequence of such edge contractions starting from G is said to be a contraction of G. A graph H is a minor of G if H is a subgraph of some contraction of G. A graph class C is minorclosed if any minor of any graph in C is also a member of C. A minorclosed graph class C is Hminorfree if H ∉ C. More generally, we use the term “Hminorfree” to refer to any minorclosed graph class that excludes some fixed graph H. A singlecrossing graph is a minor of a graph that can be drawn in the plane with at most one pair of edges crossing. A minorclosed graph class is singlecrossingminorfree if it excludes a fixed singlecrossing graph. An apex graph is a graph in which the removal of some vertex leaves a planar graph. A graph class is apexminorfree if it excludes some fixed apex graph. Bidimensional parametersFirst we define “parameters” as an alternative view on optimization problems. A parameter P is a function mapping graphs to nonnegative integers. The decision problem associated with P asks, for a given graph G and nonnegative integer k, whether P(G) ≤ k. Many optimization problems can be phrased as such a decision problem about a graph parameter P. Now we can define bidimensionality. A parameter is g(r)bidimensional (or just bidimensional) if it is at least g(r) in an r × r “gridlike graph” and if the parameter does not increase when taking either minors (g(r)minorbidimensional) or contractions (g(r)contractionbidimensional). The exact definition of “gridlike graph” depends on the class of graphs allowed and whether we are considering minor or contractionbidimensionality. For minorbidimensionality and for any Hminorfree graph class, the notion of a “gridlike graph” is defined to be the r × r grid, i.e., the planar graph with r^{2} vertices arranged on a square grid and with edges connecting horizontally and vertically adjacent vertices. For contractionbidimensionality, the notion of a “gridlike graph” is as follows:
Contractionbidimensionality is so far undefined for Hminorfree graphs (or general graphs). Examples of bidimensional parameters include the number of vertices, the diameter, and the size of various structures such as 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, unweighted TSP tour (a walk in the graph visiting all vertices), and chordal completion (fillin). For example, feedback vertex set is Ω(r^{2})minorbidimensional (and thus also contractionbidimensional) because (1) deleting or contracting an edge preserves existing feedback vertex sets, and (2) any vertex in the feedback vertex set destroys at most four squares in the r ×r grid, and there are (r−1)^{2} squares, so any feedback vertex set must have Ω(r^{2}) vertices. See [DFHT05b,DFHT04] for arguments of either contraction or minorbidimensionality for the other parameters. ResultsBidimensionality builds on the seminal Graph Minor Theory of Robertson and Seymour, by extending some mathematical results and building new algorithmic tools. The foundation for several results in bidimensionality are the following two combinatorial results. The first relates any bidimensional parameter to treewidth, while the second relates treewidth to grid minors. Theorem 1 [DH05b,DFHT04] If the parameter P is g(r)bidimensional, then for every graph G in the family associated with the parameter P, tw\nolimits(G) = O(g^{−1}(P(G))). In particular, if g(r) = Θ(r^{2}), then the bound becomes tw\nolimits(G) = O(√P(G)). Theorem 2 [DH05b] For any fixed graph H, every Hminorfree graph of treewidth w has an Ω(w) ×Ω(w) grid as a minor. The two major algorithmic results in bidimensionality are general subexponential fixedparameter algorithm, and general polynomialtime approximation scheme (PTASs): Theorem 3 [DH05b,DFHT04] Consider a g(r)bidimensional parameter P that can be computed on a graph G in h(w) n^{O(1)} time given a tree decomposition of G of width at most w. Then there is an algorithm computing P on any graph G in P's corresponding graph class, with running time [h(O(g^{−1}(k))) + 2^{O(g−1(k))}] n^{O(1)}. In particular, if g(r) = Θ(r^{2}) and h(w) = 2^{o(w2)}, then this running time is subexponential in k. Theorem 4 [DH05a] Consider a bidimensional problem satisfying the “separation property” defined in [DH05a,DH]. Suppose that the problem can be solved on a graph G with n vertices in f(n,tw\nolimits(G)) time. Suppose also that the problem can be approximated within a factor of α in g(n) time. For contractionbidimensional problems, suppose further that both of these algorithms also apply to the “generalized form” of the problem defined in [DH05a,DH]. Then there is a (1+ε)approximation algorithm whose running time is O(n f(n,O(α^{2}/ε)) + n^{3} g(n)) for the corresponding graph class of the bidimensional problem. The theorems above have many combinatorial and algorithmic applications. If we apply the parametertreewidth bound of Theorem 1 to the parameter of the number of vertices in the graph, then we prove that every Hminorfree graph on n vertices has treewidth O(√n), thus (re)proving the separator theorem for Hminorfree graphs. If we apply the parametertreewidth bound of Theorem 1 to the parameter of the diameter of the graph, then we prove a stronger form of Eppstein's diametertreewidth relation for apexminorfree graphs. (Further work shows how to further strengthen the diametertreewidth relation to linear [DH04b].) The treewidthgrid relation of Theorem 2 can be used to bound the gap between halfintegral multicommodity flow and fractional multicommodity flow in Hminorfree graphs. It also yields an O(1)approximation for treewidth in Hminorfree graphs. The subexponential fixedparameter algorithms of Theorem 3 subsume or strengthen all previous such results. These results can also be generalized to obtain fixedparameter algorithms in arbitrary graphs. The PTASs of Theorem DH05a in particular establish the first PTASs for connected dominating set and feedback vertex set even for planar graphs. For details of all of these results, see [DH]. Future DirectionsSeveral combinatorial and algorithmic open problems remain in the theory of bidimensionality and related concepts. Can the gridminor theorem for Hminorfree graphs, Theorem 2, be generalized to arbitrary graphs with a polynomial relation between treewidth and the largest grid minor? (The best relation so far is exponential.) Such polynomial generalizations have been obtained for the cases of “map graphs” and “power graphs” [DHK06]. Good gridtreewidth bounds have applications to minorbidimensional problems. Can the algorithmic results (Theorem 3 and Theorem DH05a) be generalized to solve contractionbidimensional problems beyond apexminorfree graphs? It is known that the basis for these results, Theorem 1, does not generalize [DFHT04]. Nonetheless, Theorem 3 has been generalized for one specific contractionbidimensional problem, dominating set [DFHT05b]. Can we generalize the polynomialtime approximation schemes of Theorem DH05a to more general algorithmic problems that do not correspond directly to bidimensional parameters? One general family of such problems arises when adding weights to vertices and/or edges, and the goal is e.g. to find the minimumweight dominating set. Another family of such problems arises when placing constraints (e.g., on coverage or domination) only on subsets of vertices and/or edges. Examples of such problems include Steiner tree and subset feedback vertex set. For additional open problems and details about the problems above, see [DH]. References


