# Deterministic Minimum Steiner Cut in Maximum Flow Time

Preprint · Matthew Ding, Jason Li

- Archive id: arxiv:2312.16415
- Published: 2023-12-27
- arXiv: https://arxiv.org/abs/2312.16415
- Source URL: https://arxiv.org/abs/2312.16415
- PDF: https://arxiv.org/pdf/2312.16415
- Provenance: arxiv

## 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/ε^4)}$ 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.