DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.46

Deterministic Minimum Steiner Cut in Maximum Flow Time

Authors: Matthew Ding and Jason Li

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

We devise a deterministic algorithm for minimum Steiner cut, which uses (log n)^{O(1)} maximum flow calls and additional near-linear time. This algorithm improves on Li and Panigrahi’s (FOCS 2020) algorithm, which uses (log n)^{O(1/ε⁴)} maximum flow calls and additional O(m^{1+ε}) time, for ε > 0. Our algorithm thus shows that deterministic minimum Steiner cut can be solved in maximum flow time up to polylogarithmic factors, given any black-box deterministic maximum flow algorithm. Our main technical contribution is a novel deterministic graph decomposition method for terminal vertices that generalizes all existing s-strong partitioning methods, which we believe may have future applications.

Cite as

Matthew Ding and Jason Li. Deterministic Minimum Steiner Cut in Maximum Flow Time. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ESA.2024.46,
  author =	{Ding, Matthew and Li, Jason},
  title =	{{Deterministic Minimum Steiner Cut in Maximum Flow Time}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.46},
  URN =		{urn:nbn:de:0030-drops-211174},
  doi =		{10.4230/LIPIcs.ESA.2024.46},
  annote =	{Keywords: graph algorithms, minimum cut, deterministic}
}

Search Results

Documents authored by Ding, Matthew

Deterministic Minimum Steiner Cut in Maximum Flow Time

Abstract

Cite as

Thanks for your feedback!

Could not send message