Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation

Antoine El-Hayek, Monika Henzinger, Jason Li · 2024

Read Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation by Antoine El-Hayek, Monika Henzinger, Jason Li (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15069.txt.

Description

Antoine El-Hayek, Monika Henzinger, and Jason Li give a fully dynamic approximate minimum cut in two thousand twenty-four. Graphs gain and lose edges while the minimum cut must be tracked. Past best near exact methods took far longer per update. Exact fast methods needed a promise of a large cut.

Their algorithm holds a near exact cut in subpolynomial update time. It is the first of its kind for the fully dynamic case. The core trick: small volume cuts in contracted graphs suffice. That lens shrinks the search the updates must run. Conditional lower bounds do not bar the gain.

Catalog record

CREATORAntoine El-Hayek, Monika Henzinger, Jason Li
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE168 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15069

Browse the full library · About the Tower of Babel