License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.69
URN: urn:nbn:de:0030-drops-146509
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14650/
Go to the corresponding LIPIcs Volume Portal

Maxwell, William ; Nayyeri, Amir

Generalized Max-Flows and Min-Cuts in Simplicial Complexes

pdf-format:
LIPIcs-ESA-2021-69.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{maxwell_et_al:LIPIcs.ESA.2021.69,
  author =	{Maxwell, William and Nayyeri, Amir},
  title =	{{Generalized Max-Flows and Min-Cuts in Simplicial Complexes}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{69:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14650},
  URN =		{urn:nbn:de:0030-drops-146509},
  doi =		{10.4230/LIPIcs.ESA.2021.69},
  annote =	{Keywords: Max-flow min-cut, simplicial complexes, algebraic topology}
}

Keywords: Max-flow min-cut, simplicial complexes, algebraic topology
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI