Faster maxflow via improved dynamic spectral vertex sparsifiers

DOI10.1145/3519935.3520068MaRDI QIDQ6083507zbMATH OpenOpenAlexFDO

Authors

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.00722

zbMATH Keywords

dynamic effective resistanceinterior point methodsmaximum flow

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including: 1. More efficient dynamic spectral vertex sparsification, achieved by faster length estimation of random walks in weighted graphs using Morris counters [Morris 1978, Nelson-Yu 2020]. 2. A direct reduction from detecting edges with large energy in dynamic electric flows to dynamic spectral vertex sparsifiers. 3. A procedure for turning algorithms for estimating a sequence of vectors under updates from an oblivious adversary to one that tolerates adaptive adversaries via the Gaussian-mechanism from differential privacy. Combining these pieces with modifications to prior robust interior point frameworks gives an algorithm that on graphs with $m$ edges computes a mincost flow with edge costs and capacities in $[1,U]$ in time $widetildeO(m^{3/2-1/58}lo{g}^{2}U)$. In prior and independent work, [Axiotis-Mk{a}dry-Vladu FOCS 2021] also obtained an improved algorithm for sparse mincost flows on capacitated graphs. Our algorithm implies a $widetildeO(m^{3/2-1/58}logU)$ time maxflow algorithm, improving over the $widetildeO(m^{3/2-1/328}logU)$ time maxflow algorithm of [Gao-Liu-Peng FOCS 2021].

Cited in

(6)

• High-accuracy multicommodity flows via iterative refinement
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Electrical flows for polylogarithmic competitive oblivious routing
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Maximum flow and minimum-cost flow in almost-linear time
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern

This page was built for publication: Faster maxflow via improved dynamic spectral vertex sparsifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083507)