Faster algorithms for finding small edge cuts in planar graphs

ABSTRACT

In this paper, we consider partitioning a planar graph by removing either nodes or edges. In particular, we consider a cut to be either a set of nodes or edges whose removal divides the graph into two pieces. We define the balance of a cut as the ratio of the weight of the smaller side of the cut to the total weight in the graph. Thus, the best possible balance is 1/2. We define the quotient cost of a cut as the ratio of the cost of the cut to the size of the smaller side of the cut. Thus, a costly cut with a high balance may have lower quotient cost than a less costly cut with a lower balance. Finally, we define the flux of a graph as the minimum quotient cost of any cut in the graph. We are interested in finding small cuts with high balance; either finding the cut that minimizes the quotient cost of the cut, or finding the smallest cut of some specified balance. (For balance 1/3, this problem has been called the minimum separator problem.) We present a very simple algorithm for finding 1.5 times optimal quotient node or edge cuts in planar graphs in time O(n2 min (W, C)), where W is the total weight of the graph, and C is the total cost of the graph. In fact, these cuts are only nonoptimal when they have very good balance. Thus, the algorithms either find an optimal quotient cut or a nearly optimal quotient cut with very high balance. We can greatly improve the running time if we settle for finding 3.5 times optimal quotient node and edge cuts. We can accomplish this in O(n2(log W + log C)) time. And, if we are willing to settle for O(k) times optimal solutions, we can make the running time quite fast; O(n 1+1/k log n(log W + log C)log C). If k=log m, and W and C are polynomial in n, this becomes O(n log3n). Finally, we give approximation algorithms for finding nearly optimal balanced node or edge separators in planar graphs, based on the quotient cut algorithms. These algorithms improve upon previous algorithms by being much faster, much much simpler, and by applying to node separation as well as edge separation.

REFERENCES

• 1: B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Fast constructions of sparse neighborhood covers. Unpublished Manuscript.
• 2: B. Awerbuch and D. Peleg. Sparse partitions. In 31st Symposium on Foundations of Computer Science, pages 503-513, 1990.
• 3: S.N. Bhatt and F.T. Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28(2), 1984.
• 4: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 5: G. N. Ftedrickson and R. Janardan. Separator-based startegies for efficient message routing. In #Tth Annual Symposium on Foundations of Computer Science, 1BEE, pages 428-437, 1986.
• 6: M.R. Gatey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, pages 237-267, 1976.
• 7: D. Johnson and S. Venkatesan. Partition of planar flow networks. In #th Annual Symposium on Foundations of Computer Science, 1EEE, pages 259-263, 1983.
• 8: P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
• 9: F. T. Leighton and Satish Rao. An approximate max-flow rain-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, in #8th Annual Symposium on Foundations of Computer Science, IEEE, pages 256-269, 1988.
• 10: Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103425]
• 11: c.E. L#i#on. h#-dncicnt }ayout# (for VLSI). In Proceedings of the #lts Annual Symposium on Foundations of Computer Science, October 1980.
• 12: R.J. Lipton and R.E. Tarjan. Applications of a pl# nat sepaxator theorem. SIAM Journal on Computing, 36(2):177-189, April 1979.
• 13: R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics, 8(2):177-189, April 1979.
• 14: N. Meggido. Combinatorial optimization with rational objective functions. Mathematics of Operations Re. search, 4(4):414-424, November 1979.
• 15: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 16: G. Miller and H. Gazit. A parallel algorithm for finding a separator in planar graphs. In Proceedings of the #Sth Annual S#tmposium on Foundations of Computer Science, pages 238-248, 1987.
• 17: S. Rag. Finding near optimal separators in planar graphs. In #Sth Annual Symposium on Foundations of Computer Science, 1EEE, page 225, 1987.
• 18: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory