License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.83
URN: urn:nbn:de:0030-drops-141521
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14152/
Go to the corresponding LIPIcs Volume Portal

Karczmarz, Adam

Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems

pdf-format:
LIPIcs-ICALP-2021-83.pdf (0.8 MB)

Abstract

We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically for the minimum weight cycle problem in general digraphs. One can achieve Õ(n²) amortized update time by simply invoking the fully dynamic APSP algorithm of Demetrescu and Italiano [J. ACM '04]. This bound, however, yields no improvement over the trivial recompute-from-scratch algorithm for sparse graphs.
Our first contribution is a very simple deterministic (1+ε)-approximate algorithm supporting vertex updates (i.e., changing all edges incident to a specified vertex) in conditionally near-optimal Õ(mlog{(W)}/ε) amortized time for digraphs with real edge weights in [1,W]. Using known techniques, the algorithm can be implemented on planar graphs and also gives some new sublinear fully dynamic algorithms maintaining approximate cuts and flows in planar digraphs.
Additionally, we show a Monte Carlo randomized exact fully dynamic minimum weight cycle algorithm with Õ(mn^{2/3}) worst-case update that works for real edge weights. To this end, we generalize the exact fully dynamic APSP data structure of Abraham et al. [SODA'17] to solve the multiple-pairs shortest paths problem, where one is interested in computing distances for some k (instead of all n²) fixed source-target pairs after each update. We show that in such a scenario, Õ((m+k)n^{2/3}) worst-case update time is possible.

BibTeX - Entry

@InProceedings{karczmarz:LIPIcs.ICALP.2021.83,
  author =	{Karczmarz, Adam},
  title =	{{Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14152},
  URN =		{urn:nbn:de:0030-drops-141521},
  doi =		{10.4230/LIPIcs.ICALP.2021.83},
  annote =	{Keywords: Dynamic graph algorithms, minimum weight cycle, dynamic shortest paths}
}

Keywords: Dynamic graph algorithms, minimum weight cycle, dynamic shortest paths
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI