research-article

Homology flows, cohomology cuts

Authors:

Erin W. Chambers,

Amir NayyeriAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 273 - 282

https://doi.org/10.1145/1536414.1536453

Published: 31 May 2009 Publication History

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]

R. Agarwala and D. Fernández-Baca. Weighted multidimensional search and its application to convex optimization. SIAM J. Comput. 25:83--99, 1996.

Digital Library

[2]

P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412--458, 1998.

Digital Library

[3]

P. K. Agarwal, M. Sharir, and S. Toledo. An efficient multi-dimensional searching technique and its applications. Tech. Rep. CS-1993-20, Dept. Comp. Sci., Duke Univ., August 1993. ftp://ftp.cs.duke.edu/pub/dist/techreport/1993/1993-20.ps.gz.

Digital Library

[4]

R. K. Ahuja, T. L. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

Digital Library

[5]

L. Aleksandrov and H. Djidjev. Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. Discrete Math 9(1):129--150, 1996.

Digital Library

[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]

T. C. Biedl, B. Brejová, and T. Vinar. Simplifying flow networks. Proc. 25th Symp. Math. Found. Comput. Sci., 192--201, 2000. Lecture Notes Comput. Sci. 1893, Springer-Verlag.

Digital Library

[8]

G. Borradaile. Exploiting Planarity for Network Flow and Connectivity Problems. Ph.D. thesis, Brown University, May 2008. http://www.cs.brown.edu/research/pubs/theses/phd/2008/glencora.pdf.

Digital Library

[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]

G. Borradaile, C. Kenyon-Mathieu, and P. N. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 1285--1294, 2007.

Digital Library

[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.

Digital Library

[12]

G. Borradaile and P. Klein. An O(n log n)-time algorithm for maximum st-flow in a directed planar graph. Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, 524--533, 2006.

Digital Library

[13]

G. Borradaile and P. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM !!, to appear, 2009. http://www.math.uwaterloo.ca/ glencora/downloads/maxflow-full.pdf.

Digital Library

[14]

S. Cabello and E. W. Chambers. Multiple source shortest paths in a genus g graph. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97, 2007.

Digital Library

[15]

E. W. Chambers, É. Colin de Verdière, J. Erickson, F. Lazarus, and K. Whittlesey. Splitting (complicated) surfaces is hard. Comput. Geom. Theory Appl. 41(1-2):94--110, 2008.

Digital Library

[16]

E. W. Chambers, J. Erickson, and A. Nayyeri. Minimum cuts and shortest homologous cycles. Proc. 25th Ann. ACM Symp. Comput. Geom., 2009. http://www.cs.uiuc.edu/jeffe/pubs/surfcut.html.

Digital Library

[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]

E. Cohen and N. Megiddo. Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs. J. Assoc. Comput. Mach. 40(4):791--830, 1993.

Digital Library

[20]

E. Cohen and N. Megiddo. Algorithms and complexity analysis for some flow problems. Algorithmica 11(3):320--340, 1994.

Digital Library

[21]

E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. phProc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287, 2007.

Digital Library

[22]

S. I. Diatch and D. A. Spielman. Faster lossy generalized flow via interior point algorithms. Proc. 40th ACM Symp. Theory Comput., 451--460, 2008.

Digital Library

[23]

H. N. Djidjev and S. M. Venkatesan. Planarization of graphs embedded on surfaces. Proc. 21st Workshop Graph-Theoretic Concepts Comput. Sci., 62--72, 1995. Lecture Notes Comput. Sci. 1017, Springer-Verlag.

Digital Library

[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]

D. Eppstein. Dynamic generators of topologically embedded graphs. Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608, 2003.

Digital Library

[27]

J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1):37--59, 2004.

Digital Library

[28]

J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046, 2005.

Digital Library

[29]

J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5):868--889, 2006.

Digital Library

[30]

L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian J. Math. 8(399--404), 1956.

[31]

G. N. Frederickson. Fast algorithms for shortest paths in planar graphs with applications. SIAM J. Comput. 16(6):1004--1004, 1987.

Digital Library

[32]

J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms 5(3):391--407, 1984.

Digital Library

[33]

A. V. Goldberg and S. Rao. Beyond the flow decomposition barrier. J. ACM 45(5):783--797, 1998.

Digital Library

[34]

A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. J. Assoc. Comput. Mach. 35(4):921--940, 1988.

Digital Library

[35]

M. Grohe. Isomorphism testing for embeddable graphs through definability. Proc. 32nd ACM Symp. Theory Comput., 63--72, 2000.

Digital Library

[36]

J. L. Gross and T. W. Tucker. Topological graph theory. Dover Publications, 2001.

Digital Library

[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<sup>2</sup> 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]

M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1):3--23, 1997. emsep 1.5pt

Digital Library

[44]

J. M. Hochstein and K. Weihe. Maximum s-t-flow with k crossings in O(k<sup>3</sup>n log n) time. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847, 2007.

Digital Library

[45]

J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). Proc. 6th ACM Symp. Theory Comput., 172--184, 1974.

Digital Library

[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]

H. Imai and K. Iwano. Efficient sequential and parallel algorithms for planar minimum cost flow. Proc. SIGAL Int. Symp. Algorithms, 21--30, 1990. Lecture Notes Comput. Sci. 450, Springer-Verlag.

Digital Library

[49]

A. Itai and Y. Shiloach. Maximum flow in planar networks. SIAM J. Comput. 8:135--150, 1979.

Digital Library

[50]

D. B. Johnson and S. M. Venkatesan. Partition of planar flow networks (preliminary version). Proc. 24th IEEE Symp. Found. Comput. Sci., 259--264, 1983. IEEE Computer Society.

Digital Library

[51]

S. N. Kabadi and Y. P. Aneja. ε-approximation minimization of convex functions in fixed dimension. Oper. Res. Lett. 18:171--176, 1996.

Digital Library

[52]

S. N. Kabadi and Y. P. Aneja. Equivalence of ε-approximate separation and optimization in fixed dimensions. Algorithmica 29:582--594, 2001.

Digital Library

[53]

P. Klein. Multiple-source shortest paths in planar graphs. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155, 2005.

Digital Library

[54]

P. Klein, S. Mozes, and O. Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log<sup>2</sup> n)-time algorithm. Proc. 20th Ann. ACM-SIAM Symp. Discrete Algorithms, 236--245, 2009.

Digital Library

[55]

M. Kutz. Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. Proc. 22nd Ann. ACM Symp. Comput. Geom., 430--438, 2006.

Digital Library

[56]

R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. Numer. Anal. 16:346--358, 1979.

Digital Library

[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]

N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach. 30(4):852--865, 1983.

Digital Library

[60]

G. L. Miller. Isomorphism testing for graphs of bounded genus. Proc. 12th ACM Symp. Theory Comput., 225--235, 1980.

Digital Library

[61]

G. L. Miller and J. Naor. Flow in planar graphs with multiple sources and sinks. SIAM J. Comput. 24(5):1002--10017, 1995.

Digital Library

[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]

C. H. Norton, S. A. Plotkin, and É. Tardos. Using separation algorithms in fixed dimension. J. Algorithms 13(1):79--98, 1992.

Digital Library

[65]

J. B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41(2):338--350, 1993.

Digital Library

[66]

V. Y. Pan and J. H. Reif. Fast and efficient parallel solution of sparse linear systems. SIAM J. Comput. 22(6):1227--1250, 1993.

Digital Library

[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<sup>2</sup> 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]

D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3):362--391, 1983.

Digital Library

[72]

S. Tazari and M. Müller-Hannemann. Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. Discrete Appl. Math. 157:673--684, 2009.

Digital Library

[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. Proc. 30th IEEE Symp. Found. Comput. Sci., 332--337, 1989.

Digital Library

[75]

S. M. Venkatesan. Algorithms for network flows. Ph.D. thesis, The Pennsylvania State University, 1983. Cited in jv-ppfn-83.

Digital Library

[76]

K. Weihe. Edge-disjoint $(s,t)$--paths in undirected planar graphs in linear time. J. Algorithms 23(1):121--138, 1997.

Digital Library

[77]

K. Weihe. Maximum (s, t)-flows in planar networks in O(|V| log|V|)-time. J. Comput. Syst. Sci. 55(3):454--476, 1997.

Digital Library

Cited By

Hylton AMallery BHwang JRonnenberg MLopez MChiriac OGopalakrishnan SRask T(2024)Multi-domain routing in Delay Tolerant Networks2024 IEEE Aerospace Conference10.1109/AERO58975.2024.10521176(1-20)Online publication date: 2-Mar-2024
https://doi.org/10.1109/AERO58975.2024.10521176
Fortin D(2019)Clustering Analysis of a Dissimilarity: a Review of Algebraic and Geometric RepresentationJournal of Classification10.1007/s00357-019-09315-737:1(180-202)Online publication date: 30-Mar-2019
https://doi.org/10.1007/s00357-019-09315-7
de Verdière ÉHubard Ade Mesmay ACheng SDevillers O(2014)Discrete Systolic Inequalities and Decompositions of Triangulated SurfacesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582127(335-344)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582127
Show More Cited By

Index Terms

Homology flows, cohomology cuts
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Minimum cuts and shortest homologous cycles
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

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)-...
Homology Flows, Cohomology Cuts
^† Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009)

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus $g$, with two specified vertices $s$ and $t$ and integer edge capacities that sum to $C$, ...
An output-sensitive algorithm for persistent homology

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any @C>0, it returns only those homology classes with persistence at least @C. Instead of the classical reduction via ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
360
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hylton AMallery BHwang JRonnenberg MLopez MChiriac OGopalakrishnan SRask T(2024)Multi-domain routing in Delay Tolerant Networks2024 IEEE Aerospace Conference10.1109/AERO58975.2024.10521176(1-20)Online publication date: 2-Mar-2024
https://doi.org/10.1109/AERO58975.2024.10521176
Fortin D(2019)Clustering Analysis of a Dissimilarity: a Review of Algebraic and Geometric RepresentationJournal of Classification10.1007/s00357-019-09315-737:1(180-202)Online publication date: 30-Mar-2019
https://doi.org/10.1007/s00357-019-09315-7
de Verdière ÉHubard Ade Mesmay ACheng SDevillers O(2014)Discrete Systolic Inequalities and Decompositions of Triangulated SurfacesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582127(335-344)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582127
Miller GPeng RKhanna S(2013)Approximate maximum flow on separable undirected graphsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627900(1151-1170)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627900
Fox KKhanna S(2013)Shortest non-trivial cycles in directed and undirected surface graphsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627843(352-364)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627843
Eisenstat DKlein PBoneh DRoughgarden TFeigenbaum J(2013)Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488702(735-744)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488702
Erickson JFox KNayyeri A(2012)Global minimum cuts in surface embedded graphsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095219(1309-1318)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095219
Makarychev YSidiropoulos A(2012)Planarizing an Unknown SurfaceApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-32512-0_23(266-275)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32512-0_23
Erickson JNayyeri ARandall D(2011)Minimum cuts and shortest non-separating cycles via homology coversProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133124(1166-1176)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133124
Erickson JHurtado Fvan Kreveld M(2011)Shortest non-trivial cycles in directed surface graphsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998231(236-243)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998231
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents