Minimum cuts and shortest homologous cycles

ABSTRACT

We describe the first algorithms to compute minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s,t)-cut in g^O(g) n log n time. Except for the special case of planar graphs, for which O(n log n)-time algorithms have been known for more than 20 years, the best previous time bounds for finding minimum cuts in embedded graphs follow from algorithms for general sparse graphs. A slight generalization of our minimum-cut algorithm computes a minimum-cost subgraph in every Z₂-homology class. We also prove that finding a minimum-cost subgraph homologous to a single input cycle is {NP}-hard.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Glencora Borradaile , Philip Klein, Exploiting planarity for network flow and connectivity problems, Brown University, Providence, RI, 2008
• 3: G. Borradaile, E. D. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., 171--182, 2009. Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2009/1835/.
• 4: Glencora Borradaile , Claire Kenyon-Mathieu , Philip Klein, A polynomial-time approximation scheme for Steiner tree in planar graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1285-1294, January 07-09, 2007, New Orleans, Louisiana
• 5: G. Borradaile, C. Kenyon-Mathieu, and P. N. Klein. Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon. Proc. 10th Ann. Workshop on Algorithms and Data Structures, 275--286, 2007.
• 6: Glencora Borradaile , Philip Klein, An O (n log n) algorithm for maximum st-flow in a directed planar graph, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.524-533, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109615]
• 7: Glencora Borradaile , Philip Klein, An O(n log n) algorithm for maximum st-flow in a directed planar graph, Journal of the ACM (JACM), v.56 n.2, p.1-30, April 2009 [doi>10.1145/1502793.1502798]
• 8: Sergio Cabello, Many distances in planar graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1213-1220, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109691]
• 9: Sergio Cabello , Erin W. Chambers, Multiple source shortest paths in a genus g graph, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.89-97, January 07-09, 2007, New Orleans, Louisiana
• 10: Sergio Cabello , Matt DeVos , Jeff Erickson , Bojan Mohar, Finding one tight cycle, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.527-531, January 20-22, 2008, San Francisco, California
• 11: Sergio Cabello , Bojan Mohar, Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs, Discrete & Computational Geometry, v.37 n.2, p.213-235, February 2007 [doi>10.1007/s00454-006-1292-5]
• 12: Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137918]
• 13: Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Computational Geometry: Theory and Applications, v.41 n.1-2, p.94-110, October, 2008 [doi>10.1016/j.comgeo.2007.10.010]
• 14: Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Homology flows, cohomology cuts, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536453]
• 15: C. Chen and D. Freedman. Quantifying homology classes II: Localization and stability. Preprint, 2007. http://arxiv.org/abs/0709.2512v2.
• 16: C. Chen and D. Freedman. Quantifying homology classes. Proc. 25th Ann. Symp. Theoretical Aspects Comp. Sci., 169--180, 2008. Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2008/1343/.
• 17: É. Colin de Verdière. Raccourcissement de courbes et décomposition de surfaces {Shortening of Curves and Decomposition of Surfaces}. Ph.D. thesis, University of Paris 7, Dec. 2003. http://www.di.ens.fr/colin/textes/these.html.
• 18: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 19: É. Colin de Verdière and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Proc. 11th Sympos. Graph Drawing, 478--490, 2003. Lecture Notes Comput. Sci. 2912.
• 20: É. Colin de Verdière and F. Lazarus. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33(3):507--534, 2005.
• 21: Éric Colin De Verdière , Francis Lazarus, Optimal pants decompositions and shortest homotopic cycles on an orientable surface, Journal of the ACM (JACM), v.54 n.4, p.18-es, July 2007 [doi>10.1145/1255443.1255446]
• 22: Erik D. Demaine , MohammadTaghi Hajiaghayi , Bojan Mohar, Approximation algorithms via contraction decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.278-287, January 07-09, 2007, New Orleans, Louisiana
• 23: Tamal K. Dey , Kuiyu Li , Jian Sun, On Computing Handle and Tunnel Loops, Proceedings of the 2007 International Conference on Cyberworlds, p.357-366, October 24-26, 2007 [doi>10.1109/CW.2007.49]
• 24: Tamal K. Dey , Kuiyu Li , Jian Sun , David Cohen-Steiner, Computing geometry-aware handle and tunnel loops in 3D models, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 25: D. Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms and Applications 3(3):1--27, 1999.
• 26: D. Eppstein. Diameter and treewidth in minor-closed graph families. phAlgorithmica 27:275--291, 2000.
• 27: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1):37--59, 2004.
• 28: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 29: J. Erickson and P. Worah. Computing the shortest essential cycle. Preprint, November 2008. http://www.cs.uiuc.edu/jeffe/pubs/essential.html.
• 30: Jittat Fakcharoenphol , Satish Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, Journal of Computer and System Sciences, v.72 n.5, p.868-889, August 2006 [doi>10.1016/j.jcss.2005.05.007]
• 31: L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian J. Math. 8(399--404), 1956.
• 32: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 33: Merrick L. Furst , Jonathan L. Gross , Lyle A. McGeoch, Finding a maximum-genus graph imbedding, Journal of the ACM (JACM), v.35 n.3, p.523-534, July 1988 [doi>10.1145/44483.44485]
• 34: Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
• 35: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 36: Martin Grohe, Isomorphism testing for embeddable graphs through definability, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.63-72, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335313]
• 37: Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
• 38: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 39: T. E. Harris and F. S. Ross. Fundamentals of a method for evaluating rail net capacities. Tech. rep., The RAND Corporation, Santa Monica, California, October 24 1955. Cited in s-hco-05.
• 40: R. Hassin and D. B. Johnson. An O(n log² n) algorithm for maximum flow in undirected planar networks. SIAM J. Comput. 14(3):612--624, 1985.
• 41: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http://www.math.cornell.edu/hatcher/.
• 42: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 43: Jan M. Hochstein , Karsten Weihe, Maximum s-t-flow with k crossings in O(k³n log n) time, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.843-847, January 07-09, 2007, New Orleans, Louisiana
• 44: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 45: Hiroshi Imai , Kazuo Iwano, Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow, Proceedings of the International Symposium on Algorithms, p.21-30, August 16-18, 1990
• 46: Piotr Indyk , Anastasios Sidiropoulos, Probabilistic embeddings of bounded genus graphs into planar graphs, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247107]
• 47: A. Itai and Y. Shiloach. Maximum flow in planar networks. SIAM J. Comput. 8:135--150, 1979.
• 48: L. Janiga and V. Koubek. Minimum cut in directed planar networks. Kybernetika 28(1):37--49, 1992.
• 49: Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250848]
• 50: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 51: Philip Klein , Shay Mozes , Oren Weimann, Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log² n)-time algorithm, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.236-245, January 04-06, 2009, New York, New York
• 52: Martin Kutz, Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137919]
• 53: R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. Numer. Anal. 16:346--358, 1979.
• 54: M. Mares. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum 40(3):315--320, 2004.
• 55: S. T. McCormick, M. R. Rao, and G. Rinaldi. Easy and difficult objective functions for max cut. Math. Program., Ser. B 94:459--466, 2003.
• 56: Gary Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.225-235, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804670]
• 57: Gary L. Miller, Flow in Planar Graphs with Multiple Sources and Sinks, SIAM Journal on Computing, v.24 n.5, p.1002-1017, Oct. 1995 [doi>10.1137/S0097539789162997]
• 58: B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
• 59: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 60: Victor Pan , John Reif, Fast and efficient parallel solution of sparse linear systems, SIAM Journal on Computing, v.22 n.6, p.1227-1250, Dec. 1993 [doi>10.1137/0222073]
• 61: D. Pe’er. On minimum spanning trees. Master's thesis, Hebrew University, 1998. http://www.math.ias.edu/avi/STUDENTS/dpthesis.pdf.
• 62: J. Reif. Minimum s-t cut of a planar undirected network in O(n log² n) time. SIAM J. Comput. 12:71--81, 1983.
• 63: G. Ringel. Map Color Theorem. Springer-Verlag, 1974.
• 64: G. Ringel and J. W. T. Youngs. Solution of the Heawood map-coloring problem. Proc. Nat. Acad. Sci. USA 60:438--445, 1968.
• 65: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer-Verlag, 2003.
• 66: A. Schrijver. On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, 1--68, 2005. Elsevier.
• 67: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 68: J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.
• 69: Siamak Tazari , Matthias Müller-Hannemann, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Discrete Applied Mathematics, v.157 n.4, p.673-684, February, 2009 [doi>10.1016/j.dam.2008.08.002]
• 70: C. Thomassen, Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory Series B, v.48 n.2, p.155-177, Apr. 1990 [doi>10.1016/0095-8956(90)90115-G]
• 71: P. M. Vaidya, Speeding-up linear programming using fast matrix multiplication, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.332-337, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63499]
• 72: Karsten Weihe, Maximum (s,t)-flows in planar networks in O(|V| log |V|) time, Journal of Computer and System Sciences, v.55 n.3, p.454-475, Dec. 1997 [doi>10.1006/jcss.1997.1538]
• 73: Afra J. Zomorodian , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2005
• 74: Afra Zomorodian , Gunnar Carlsson, Localized Homology, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007, p.189-198, June 13-15, 2007 [doi>10.1109/SMI.2007.25]

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
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance

Keywords:
computational topology, topological graph theory