2026-07-22T18:55:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14144 2024-03-06T10:53:35Z ddc:004 open_access

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths Gu, Yuzhou Polak, Adam Vassilevska Williams, Virginia Xu, Yinzhan APSP Min-Plus Product Range Mode Single-Source Replacement Paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuzhou Gu and Adam Polak and Virginia Vassilevska Williams and Yinzhan Xu 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.75 urn:nbn:de:0030-drops-141440 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.75 eng https://creativecommons.org/licenses/by/4.0/legalcode