 |
Research Abstracts Home |  |
CSAIL Digital Archive |  |
Research Activities |  |
CSAIL Home |  |
|
Research
Abstracts - 2007
|
|
PTASs for Planar Graphs and GeneralizationsErik D. Demaine & MohammadTaghi HajiaghayiContextThere are two main general approaches for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs and their generalizations. (A graph is planar if it can be drawn in the plane (or the sphere) without crossings. For definitions of other related graph classes, see the research abstract on Bidimensionality.) Lipton and Tarjan [LT79,LT80] introduced the first approach, which is based on planar separators. The first step in this approach is to find a separator of O(√n) vertices or edges, where n is the size of the graph, whose removal splits the graph into two or more pieces each of which is a constant fraction smaller than the original graph. Then we recurse in each piece, building a recursion tree of separators, and stop when the pieces have some constant size such as 1/ε. The problem can be solved on these pieces by brute force, and then it remains to combine the solutions up the recursion tree. The induced error can often be bounded in terms of the total size of all separators, which in turn can be bounded by ε n. If the optimal solution is at least some constant factor times n, this approach often leads to a PTAS. There are two limitations to this planar-separator approach. First, it requires that the optimal solution is at least some constant factor times n; otherwise, the cost incurred by the separators can be far larger than the desired optimal solution. Such a bound is possible in some problems after some graph pruning (linear kernelization), e.g., independent set [LT80], vertex cover [NTN81], and forms of the Traveling Salesman Problem [GKP95]. But, for example, Grohe [Gro03] states that dominating set is a problem "to which the technique based on the separator theorem does not apply". Second, the approximation algorithms resulting from planar separators are often impractical because of large constant factors. For example, to achieve an approximation ratio of just 2, the base case requires exhaustive solution of graphs of up to 22400 vertices. Baker [Bak94] introduced the second approach to address the second limitation, but it also addresses the first limitation to a certain extent. This approach is based on decomposition into overlapping subgraphs of bounded outerplanarity. Specifically, Baker's approach starts with a planar embedding of the planar graph. Then it divides vertices into layers by iteratively removing vertices on the outer face of the graph: layer j consists of the vertices removed at the jth iteration. If we now remove the layers congruent to i modulo k, for any choice of i, the graph separates into connected components each with at most k consecutive layers, and hence the graph becomes k-outerplanar. Many NP-complete problems can be solved on k-outerplanar graphs for fixed k using dynamic programming (in particular, such graphs have bounded treewidth). Baker's approximation algorithm computes these optimal solutions for each choice i of the congruence class of layers to remove, and returns the best solution among these k solutions. The key argument for maximization problems considers the optimal solution to the full graph, and argues that the removal of one of the k congruence classes of layers must remove at most a 1/k fraction of the optimal solution, so the returned solution must be within a 1+1/k factor of optimal. A more delicate argument handles minimization problems as well. For many problems, such as maximum independent set, minimum dominating set, and minimum vertex cover, Baker's approach obtains a (1+ε)-approximation algorithms with running time of 2O(1/ε) nO(1) on planar graphs. Eppstein [Epp00] generalized Baker's approach to a broader class of graphs called graphs of bounded local treewidth, i.e., where the treewidth of the subgraph induced by the set of vertices at distance at most r from any vertex is bounded above by some function f(r) independent of n. The main differences in Eppstein's approach are replacing the concept of bounded outerplanarity with the concept of bounded treewidth, where dynamic programming can still solve many problems, and labeling layers according to a simple breadth-first search. This approach has led to PTASs for hereditary maximization problems such as maximum independent set and maximum clique, maximum triangle matching, maximum H-matching, maximum tile salvage, minimum vertex cover, minimum dominating set, minimum edge-dominating set, minimum color sum, and subgraph isomorphism for a fixed pattern [Epp00,DHN+04,HN,DHK05]. Frick and Grohe [FG01] also developed a general framework for deciding any property expressible in first-order logic in graphs of bounded local treewidth. ResultsThe foundation of these results is Eppstein's characterization of minor-closed families of graphs with bounded local treewidth [Epp00]. Specifically, he showed that a minor-closed family has bounded local treewidth if and only if it excludes some apex graph, a graph with a vertex whose removal leaves a planar graph. Unfortunately, the initial proof of this result brought Eppstein's approach back to the realm of impracticality, because his bound on local treewidth in a general apex-minor-free graph is doubly exponential in r: 22O(r). Fortunately, this bound could be improved to 2O(r) [DH04a] and even the optimal O(r) [DH04b]. The latter bound restores Baker's 2O(1/ε) nO(1) running time for (1+ε)-approximation algorithms, now for all apex-minor-free graphs. Another way to view the necessary decomposition of Baker's and Eppstein's approaches is that the vertices or edges of the graph can be split into any number k of pieces such that deleting any one of the pieces results in a graph of bounded treewidth (where the bound depends on k). Such decompositions in fact exist for arbitrary graphs excluding any fixed minor H [DDO+04], and they can be found in polynomial time [DHK05]. This approach generalizes the Baker-Eppstein PTASs described above to handle general H-minor-free graphs. This decomposition approach is effectively limited to deletion-closed problems, whose optimal solution only improves when deleting edges or vertices from the graph. Another decomposition approach targets contraction-closed problems, whose optimal solution only improves when contracting edges. These problems include classic problems such as dominating set and its variations, the Traveling Salesman Problem, subset TSP, minimum Steiner tree, and minimum-weight c-edge-connected submultigraph. PTASs have been obtained for these problems in planar graphs [Kle05,Kle06,BKMK07] and in bounded-genus graphs [DHM07] by showing that the edges can be decomposed into any number k of pieces such that contracting any one piece results in a bounded-treewidth graph (where the bound depends on k). Most applications of Baker's approach have been limited to optimization problems arising from “local” properties (such as those definable in first-order logic). Intuitively, such local properties can be decided by locally checking every constant-size neighborhood. In [DH05], Baker's approach is generalized to obtain PTASs for nonlocal problems, in particular, connected dominating set. This generalization requires the use of two different techniques. The first technique is to use an ε-fraction of a constant-factor (or even logarithmic-factor) approximation to the problem as a “backbone” for achieving the needed nonlocal property. The second technique is to use subproblems that overlap by Θ(log n) layers instead of the usual Θ(1) in Baker's approach. Despite this advance in applying Baker's approach to more general problems, the planar-separator approach can still handle some different problems. Recall, though, that the planar-separator approach was limited to problems in which the optimal solution is at least some constant factor times n. This limitation has been overcome for a wide range of problems [DH05], in particular obtaining a PTAS for feedback vertex set, to which neither Baker's approach nor the planar-separator approach could previously apply. This result is based on evenly dividing the optimum solution instead of the whole graph, using a relation between treewidth and the optimal solution value to bound the treewidth of the graph, and thus obtaining an O(√OPT) separator instead of an O(√n) separator. The O(√OPT) bound on treewidth follows from the bidimensionality theory described in the research abstract on Bidimensionality. Roughly evenly dividing the optimum solution (without knowing the optimum solution) is possible using existing constant-factor (or even logarithmic-factor) approximations for the problem. At the base of the recursion, pieces no longer have bounded size but do have bounded treewidth, so fast fixed-parameter algorithms can be used to construct optimal solutions. Future DirectionsAn intriguing direction for future research is to build a general theory for PTASs of subset problems. Although PTASs for subset TSP and Steiner tree have recently been obtained for planar graphs [Kle06,BKMK07], there remain several open problems of this kind, such as subset feedback vertex set. Another instructive problem is to understand the extent to which Baker's approach can be applied to nonlocal problems. Again we have an example of how to modify the approach to handle the nonlocal problem of connected dominating set [DH05], but for example the only known PTAS for feedback vertex set in planar graphs follows the separator approach. References
|
 |
||
|
