Constant factor approximation of vertex-cuts in planar graphs

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• n^3+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.

REFERENCES

• 1: Cristinel Ababei , Navaratnasothie Selvakkumaran , Kia Bazargan , George Karypis, Multi-objective circuit partitioning for cutsize and path-based delay minimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.181-185, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774599]
• 2: Noga Alon , Paul Seymour , Robin Thomas, Planar Separators, SIAM Journal on Discrete Mathematics, v.7 n.2, p.184-193, May 1994 [doi>10.1137/S0895480191198768]
• 3: Eyal Amir, Efficient Approximation for Triangulation of Minimum Treewidth, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.7-15, August 02-05, 2001
• 4: E. Amir and S. McIlraith. Partition-based logical reasoning. In Proc. 7th Int'l Conference on Principles of Knowledge Representation and Reasoning, pages 389--400. Morgan Kaufmann, 2000.
• 5: Thang Nguyen Bui , Curt Jones, Finding good approximate vertex and edge partitions is NP-hard, Information Processing Letters, v.42 n.3, p.153-159, May 25, 1992 [doi>10.1016/0020-0190(92)90140-Q]
• 6: R. Diestel. Graph theory. Springer-Verlag, New York, second edition, 2000.
• 7: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 8: Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
• 9: Naveen Garg , Huzur Saran , Vijay V. Vazirani, Finding Separator Cuts in Planar Graphs within Twice the Optimal, SIAM Journal on Computing, v.29 n.1, p.159-179, Feb. 2000 [doi>10.1137/S0097539794271692]
• 10: R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309--311, 1978.
• 11: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 12: S. L. Lauritzen and D.J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society B, 50(2):157--224, 1988.
• 13: F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 422--431, October 1988.
• 14: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 15: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177--189, 1979.
• 16: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 17: B. Mohar, Isoperimetric numbers of graphs, Journal of Combinatorial Theory Series B, v.47 n.3, p.274-291, Dec. 1989 [doi>10.1016/0095-8956(89)90029-4]
• 18: James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167284]
• 19: S. Rao. Finding near optimal separators in planar graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 225--237. IEEE, 1987.
• 20: Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129735]
• 21: N. Robertson and P. D. Seymour. Graph minors. II: algorithmic aspects of treewidth. J. Algorithms, 7:309--322, 1986.
• 22: P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217--241, 1994.
• 23: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 24: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 25: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, balanced cut, planar graph, planar separator, quotient cut, vertex separator