pipette
ENEnglish

Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators

Arnold Filtser, Gramoz Goranci, Ali Momeni, Neel Patel, Maximilian Probst Gutenberg

Preprint

En palabras de los autores

We study the fully-dynamic all-pairs minimum cut problem on planar graphs. Given an -vertex undirected planar graph undergoing edge insertions and deletions, the goal is to efficiently process these updates while supporting - minimum cut queries for any pair of vertices and . We give a -approximate dynamic algorithm that supports edge updates and minimum cut queries in time, for any . For general graphs, previous results either are limited to partially dynamic settings or achieve only logarithmic-factor approximations. The main conceptual and technical contribution is to show that a suitable adaptation of the planar emulator of Chang, Krauthgamer, and Tan~[STOC'22] satisfies the stronger pattern emulator introduced by Chen and Tan~[ICALP'25]. This leads almost immediately to a nearly linear-time construction of pattern emulators, which, when combined with the recent fully dynamic -approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg~[FOCS'24], yields our result.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.