Constant factor approximation of vertex-cuts in planar graphs
Authors:
Open Access
- 9 June 2003
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 90-99
Abstract
We devise the first constant factor approximation algorithm for minimum quotient vertex-cuts in planar graphs. Our algorithm achieves approximation ratio 1+4/3(1+ε) with running time O(W• n3+2/ε), where W is the total weight of the vertices. The approximation ratio improves to 4/3(1+ε+o(1)) if there is an optimal quotient vertex-cut (A*,B*,C*) where the weight of C* is of low order compared to those of A* and B*; this holds, for example, when the input graph has uniform weights and costs. The ratio further improves to 1+ε+o(1) if, in addition, min[w(A*),w(B*)] ≤ 1/3 W.We use our algorithm for quotient vertex-cuts to achieve the first constant-factor pseudo-approximation for vertex separators in planar graphs.Our technical contribution is two-fold. First, we prove a structural theorem for planar graphs, showing the existence of a near-optimal quotient vertex-cut whose high-level structure is that of a bounded-depth tree. Second, we develop an algorithm that optimizes over such complex structures in running time that depends (exponentially) not on the size of the structure, but rather only on its depth. These techniques may be applicable in other problems.Keywords
This publication has 19 references indexed in Scilit:
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Finding Separator Cuts in Planar Graphs within Twice the OptimalSIAM Journal on Computing, 1999
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- Call routing and the ratcatcherCombinatorica, 1994
- Planar SeparatorsSIAM Journal on Discrete Mathematics, 1994
- Finding good approximate vertex and edge partitions is NP-hardInformation Processing Letters, 1992
- Isoperimetric numbers of graphsJournal of Combinatorial Theory, Series B, 1989
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978