Document Open Access Logo

Generalized Max-Flows and Min-Cuts in Simplicial Complexes

Authors William Maxwell, Amir Nayyeri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.69.pdf
  • Filesize: 0.68 MB
  • 16 pages

Document Identifiers

Author Details

William Maxwell
  • Oregon State University, Corvallis, OR, USA
Amir Nayyeri
  • Oregon State University, Corvallis, OR, USA

Funding

This research was supported in part by NSF grants CCF-1941086, CCF-1816442, and CCF-1617951.

Cite As Get BibTex

William Maxwell and Amir Nayyeri. Generalized Max-Flows and Min-Cuts in Simplicial Complexes. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.69

Abstract

We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By viewing flows and cuts topologically in terms of the simplicial (co)boundary operator we can state these problems as linear programs and show that they are dual to one another. Unlike graphs, complexes with integral capacity constraints may have fractional max-flows. We show that computing a maximum integral flow is NP-hard. Moreover, we give a combinatorial definition of a simplicial cut that seems more natural in the context of optimization problems and show that computing such a cut is NP-hard. However, we provide conditions on the simplicial complex for when the cut found by the linear program is a combinatorial cut. For d-dimensional simplicial complexes embedded into ℝ^{d+1} we provide algorithms operating on the dual graph: computing a maximum flow is dual to computing a shortest path and computing a minimum cut is dual to computing a minimum cost circulation. Finally, we investigate the Ford-Fulkerson algorithm on simplicial complexes, prove its correctness, and provide a heuristic which guarantees it to halt.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
Keywords
  • Max-flow min-cut
  • simplicial complexes
  • algebraic topology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., USA, 1993. Google Scholar
  2. Glencora Borradaile and Philip Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2), 2009. URL: https://doi.org/10.1145/1502793.1502798.
  3. Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In Proc. 25th Ann. Symp. Comput. Geom., pages 377-385, 2009. Google Scholar
  4. Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Homology flows, cohomology cuts. SIAM Journal on Computing, 41(6):1605-1634, 2012. URL: https://doi.org/10.1137/090766863.
  5. Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. SIAM J. Comput., 40(4):1026-1044, 2011. URL: https://doi.org/10.1137/100800245.
  6. Tamal K. Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, page 2587–2606, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  7. Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. Cuts and flows of cell complexes. Journal of Algebraic Combinatorics, 41:969-999, 2015. Google Scholar
  8. Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. Simplicial and cellular trees, pages 713-752. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-24298-9_28.
  9. Jeff Erickson. Algorithms. http://algorithms.wtf, 2019.
  10. Jeff Erickson and Amir Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1166-1176, 2011. Google Scholar
  11. Arthur F. Veinott, Jr. and George B. Dantzig. Integral extreme points. SIAM Review, 10(3):371-372, July 1968. URL: https://doi.org/10.1137/1010063.
  12. Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs with applications. SIAM J. Comput., 16(6):1004-1004, 1987. Google Scholar
  13. Refael Hassin. Maximum flow in (s, t) planar networks. Inf. Process. Lett., 13:107, 1981. Google Scholar
  14. Refael Hassin and Donald B. Johnson. An O(nlog² n) algorithm for maximum flow in undirected planar networks. SIAM J. Comput., 14(3):612-624, 1985. Google Scholar
  15. Sergei Ivanov (https://mathoverflow.net/users/4354/sergei ivanov). computational complexity. MathOverflow. URL:https://mathoverflow.net/q/118428 (version: 2013-01-09). URL: http://arxiv.org/abs/https://mathoverflow.net/q/118428.
  16. Oscar H Ibarra, Shlomo Moran, and Roger Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms, 3(1):45-56, 1982. URL: https://doi.org/10.1016/0196-6774(82)90007-4.
  17. Alon Itai and Yossi Shiloach. Maximum flow in planar networks. SIAM J. Comput., 8:135-150, 1979. Google Scholar
  18. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proc. 43rd Ann. ACM Symp. Theory Comput., pages 313-322, 2011. Google Scholar
  19. Fabian Latorre. The maxflow problem and a generalization to simplicial complexes, 2012. URL: http://arxiv.org/abs/arXiv:1212.1406.
  20. Lek-Heng Lim. Hodge Laplacians on graphs. SIAM Review, 63(3):685-715, 2020. Google Scholar
  21. Sarah Morell, Ina Seidel, and Stefan Weltge. Minimum-cost integer circulations in given homology classes, 2020. URL: http://arxiv.org/abs/1911.10912.
  22. John Reif. Minimum s-t cut of a planar undirected network in O(nlog² n) time. SIAM J. Comput., 12:71-81, 1983. Google Scholar
  23. Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., USA, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact