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.75
URN: urn:nbn:de:0030-drops-141440
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14144/
Go to the corresponding LIPIcs Volume Portal

Gu, Yuzhou ; Polak, Adam ; Vassilevska Williams, Virginia ; Xu, Yinzhan

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

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

Abstract

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic time algorithms for structured instances of APSP and problems equivalent to it, such as the Min-Plus matrix product.
A natural structured version of Min-Plus product is Monotone Min-Plus product which has been studied in the context of the Batch Range Mode [SODA'20] and Dynamic Range Mode [ICALP'20] problems. This paper improves the known algorithms for Monotone Min-Plus Product and for Batch and Dynamic Range Mode, and establishes a connection between Monotone Min-Plus Product and the Single Source Replacement Paths (SSRP) problem on an n-vertex graph with potentially negative edge weights in {-M, …, M}.
SSRP with positive integer edge weights bounded by M can be solved in Õ(Mn^ω) time, whereas the prior fastest algorithm for graphs with possibly negative weights [FOCS'12] runs in O(M^{0.7519} n^{2.5286}) time, the current best running time for directed APSP with small integer weights. Using Monotone Min-Plus Product, we obtain an improved O(M^{0.8043} n^{2.4957}) time SSRP algorithm, showing that SSRP with constant negative integer weights is likely easier than directed unweighted APSP, a problem that is believed to require n^{2.5-o(1)} time.
Complementing our algorithm for SSRP, we give a reduction from the Bounded-Difference Min-Plus Product problem studied by Bringmann et al. [FOCS'16] to negative weight SSRP. This reduction shows that it might be difficult to obtain an Õ(M n^{ω}) time algorithm for SSRP with negative weight edges, thus separating the problem from SSRP with only positive weight edges.

BibTeX - Entry

@InProceedings{gu_et_al:LIPIcs.ICALP.2021.75,
  author =	{Gu, Yuzhou and Polak, Adam and Vassilevska Williams, Virginia and Xu, Yinzhan},
  title =	{{Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{75:1--75: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/14144},
  URN =		{urn:nbn:de:0030-drops-141440},
  doi =		{10.4230/LIPIcs.ICALP.2021.75},
  annote =	{Keywords: APSP, Min-Plus Product, Range Mode, Single-Source Replacement Paths}
}

Keywords: APSP, Min-Plus Product, Range Mode, Single-Source Replacement 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