Homology flows, cohomology cuts

ABSTRACT

We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in O(g⁷ n log² n log² C) time for integer capacities that sum to C, or in (g log n)^O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

REFERENCES

• 1: Richa Agarwala , David Fernandez-Baca, Weighted Multidimensional Search and itsApplication to Convex Optimization, SIAM Journal on Computing, v.25 n.1, p.83-99, Feb. 1996 [doi>10.1137/S0097539792241928]
• 2: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• 3: K P Agarwal , Micha Sharir , Sivan Toledo, An Efficient Multi-Dimensional Searching Technique and itsApplications, Duke University, Durham, NC, 1993
• 4: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 5: L. Aleksandrov , H. Djidjev, Linear Algorithms for Partitioning Embedded Graphs of BoundedGenus, SIAM Journal on Discrete Mathematics, v.9 n.1, p.129-150, Feb. 1996 [doi>10.1137/S0895480194272183]
• 6: Y. P. Aneja and S. N. Kabadi. Polynomial algorithms for Lagrangean relaxations in combinatorial problems. Faculty of Business Working Paper Series W91-03, University of Windsor, 1991. Cited in ka-eapof-01.
• 7: Therese C. Biedl , Brona Brejová , Tomás Vinar, Simplifying Flow Networks, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.192-201, September 01, 2000
• 8: Glencora Borradaile , Philip Klein, Exploiting planarity for network flow and connectivity problems, Brown University, Providence, RI, 2008
• 9: 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/.
• 10: 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
• 11: 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.
• 12: 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]
• 13: 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]
• 14: 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
• 15: 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]
• 16: Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Minimum cuts and shortest homologous cycles, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542426]
• 17: E. Cohen. Combinatorial Algorithms for Optimization Problems. Ph.D. thesis, Dept. Comput. Sci., Stanford Univ., June 1991. Tech. Report STAN-CS-91-1366.
• 18: E. Cohen and N. Megiddo. Maximizing concave functions in fixed dimension. Complexity in Numerical Optimization, 74--87, 1993. World Scientific.
• 19: Edith Cohen , Nimrod Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs, Journal of the ACM (JACM), v.40 n.4, p.791-830, Sept. 1993 [doi>10.1145/153724.153727]
• 20: E. Cohen and N. Megiddo. Algorithms and complexity analysis for some flow problems. Algorithmica 11(3):320--340, 1994.
• 21: 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
• 22: Samuel I. Daitch , Daniel A. Spielman, Faster approximate lossy generalized flow via interior point algorithms, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374441]
• 23: Hristo Dijdjev , Shankar M. Venkatesan, Planarization of Graphs Embedded on Surfaces, Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, p.62-72, June 20-22, 1995
• 24: D. Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms and Applications 3(3):1--27, 1999.
• 25: D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica 27:275--291, 2000.
• 26: David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 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: 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]
• 30: L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian J. Math. 8(399--404), 1956.
• 31: 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]
• 32: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 33: 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]
• 34: 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]
• 35: 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]
• 36: Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
• 37: M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169--197, 1981.
• 38: M. Grötschel, L. Lovász, and A. Schrijver. phGeometric Algorithms and Combinatorial Optimization, 2nd edition. Algorithms and Combinatorics 2. Springer-Verlag, 1993.
• 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. Maximum flow in $(s,t)$ planar networks. Inform. Proc. Lett. 13:107, 1981.
• 41: 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.
• 42: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http://www.math.cornell.edu/hatcher/.
• 43: 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]
• 44: 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
• 45: 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]
• 46: J. P. Hutchinson. On genus-reducing and planarizing algorithms for embedded graphs. Graphs and Algorithms, Proc. AMS-IMS-SIAM Joint Summer Res. Conf., 19--26, 1989. Contemporary Mathematics 89, American Mathematical Society.
• 47: J. P. Hutchinson and G. L. Miller. Deleting vertices to make graphs of positive genus planar. Discrete Algorithms and Complexity Theory, Proceedings of the Japan-US Joint Seminar, Kyoto, Japan, 81--98, 1987. Academic Press.
• 48: 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
• 49: A. Itai and Y. Shiloach. Maximum flow in planar networks. SIAM J. Comput. 8:135--150, 1979.
• 50: Donald B. Johnson , Shankar M. Venkatesan, Partition of planar flow networks, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.259-264, November 07-09, 1983 [doi>10.1109/SFCS.1983.44]
• 51: S. N. Kabadi and Y. P. Aneja. ε-approximation minimization of convex functions in fixed dimension. Oper. Res. Lett. 18:171--176, 1996.
• 52: S. N. Kabadi and Y. P. Aneja. Equivalence of ε-approximate separation and optimization in fixed dimensions. Algorithmica 29:582--594, 2001.
• 53: 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
• 54: 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
• 55: 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]
• 56: R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. Numer. Anal. 16:346--358, 1979.
• 57: M. Mares. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum 40(3):315--320, 2004.
• 58: W. S. Massey. A basic course in algebraic topology. Springer-Verlag, 1991. emsep 0.6pt
• 59: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 60: 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]
• 61: 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]
• 62: B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
• 63: J. R. Munkres. Topology, 2nd edition. Prentice-Hall, 2000.
• 64: Carolyn Haibt Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Journal of Algorithms, v.13 n.1, p.79-98, March 1992 [doi>10.1016/0196-6774(92)90006-X]
• 65: James B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, v.41 n.2, p.338-350, March–April 1993 [doi>10.1287/opre.41.2.338]
• 66: 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]
• 67: D. Pe'er. On minimum spanning trees. Master's thesis, Hebrew University, 1998. http://www.math.ias.edu/ avi/STUDENTS/dpthesis.pdf.
• 68: J. Reif. Minimum s-t cut of a planar undirected network in O(n log² n) time. SIAM J. Comput. 12:71--81, 1983.
• 69: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer-Verlag, 2003.
• 70: A. Schrijver. On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, 1--68, 2005. Elsevier.
• 71: 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]
• 72: 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]
• 73: S. Toledo. Maximizing non-linear concave functions in fixed dimension. Complexity in Numerical Optimization, 429--447, 1993. World Scientific.
• 74: 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]
• 75: Shankar M. Venkatesan, Algorithms for network flows, The Pennsylvania State University, 1983
• 76: Karsten Weihe, Edge-disjoint (s,t)-paths in undirected planar graphs in linear time, Journal of Algorithms, v.23 n.1, p.121-138, April 1997 [doi>10.1006/jagm.1996.0831]
• 77: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional 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

General Terms:
Algorithms, Performance

Keywords:
combinatorial optimization, computational topology