 |
Research Abstracts Home |  |
CSAIL Digital Archive |  |
Research Activities |  |
CSAIL Home |  |
|
Research
Abstracts - 2007
|
|
Bidimensionality TheoryErik D. Demaine & MohammadTaghi HajiaghayiOverviewThe theory of bidimensionality provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for a broad range of NP-hard 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 Ω(k2), 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 minor-closed if any minor of any graph in C is also a member of C. A minor-closed graph class C is H-minor-free if H ∉ C. More generally, we use the term “H-minor-free” to refer to any minor-closed graph class that excludes some fixed graph H. A single-crossing graph is a minor of a graph that can be drawn in the plane with at most one pair of edges crossing. A minor-closed graph class is single-crossing-minor-free if it excludes a fixed single-crossing graph. An apex graph is a graph in which the removal of some vertex leaves a planar graph. A graph class is apex-minor-free 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 “grid-like graph” and if the parameter does not increase when taking either minors (g(r)-minor-bidimensional) or contractions (g(r)-contraction-bidimensional). The exact definition of “grid-like graph” depends on the class of graphs allowed and whether we are considering minor- or contraction-bidimensionality. For minor-bidimensionality and for any H-minor-free graph class, the notion of a “grid-like graph” is defined to be the r × r grid, i.e., the planar graph with r2 vertices arranged on a square grid and with edges connecting horizontally and vertically adjacent vertices. For contraction-bidimensionality, the notion of a “grid-like graph” is as follows:
Contraction-bidimensionality is so far undefined for H-minor-free 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 vertex-removal parameters, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, unweighted TSP tour (a walk in the graph visiting all vertices), and chordal completion (fill-in). For example, feedback vertex set is Ω(r2)-minor-bidimensional (and thus also contraction-bidimensional) 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 Ω(r2) vertices. See [DFHT05b,DFHT04] for arguments of either contraction- or minor-bidimensionality 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) = Θ(r2), then the bound becomes tw\nolimits(G) = O(√P(G)). Theorem 2 [DH05b] For any fixed graph H, every H-minor-free graph of treewidth w has an Ω(w) ×Ω(w) grid as a minor. The two major algorithmic results in bidimensionality are general subexponential fixed-parameter algorithm, and general polynomial-time 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) nO(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))) + 2O(g−1(k))] nO(1). In particular, if g(r) = Θ(r2) and h(w) = 2o(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 contraction-bidimensional 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/ε)) + n3 g(n)) for the corresponding graph class of the bidimensional problem. The theorems above have many combinatorial and algorithmic applications. If we apply the parameter-treewidth bound of Theorem 1 to the parameter of the number of vertices in the graph, then we prove that every H-minor-free graph on n vertices has treewidth O(√n), thus (re)proving the separator theorem for H-minor-free graphs. If we apply the parameter-treewidth bound of Theorem 1 to the parameter of the diameter of the graph, then we prove a stronger form of Eppstein's diameter-treewidth relation for apex-minor-free graphs. (Further work shows how to further strengthen the diameter-treewidth relation to linear [DH04b].) The treewidth-grid relation of Theorem 2 can be used to bound the gap between half-integral multicommodity flow and fractional multicommodity flow in H-minor-free graphs. It also yields an O(1)-approximation for treewidth in H-minor-free graphs. The subexponential fixed-parameter algorithms of Theorem 3 subsume or strengthen all previous such results. These results can also be generalized to obtain fixed-parameter 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 grid-minor theorem for H-minor-free 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 grid-treewidth bounds have applications to minor-bidimensional problems. Can the algorithmic results (Theorem 3 and Theorem DH05a) be generalized to solve contraction-bidimensional problems beyond apex-minor-free 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 contraction-bidimensional problem, dominating set [DFHT05b]. Can we generalize the polynomial-time 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 minimum-weight 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
|
 |
||
|
