Negative-Weight Single-Source Shortest Paths in Near-linear Time

Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(m log8 (n) log W) time when edge weights are integral and can be negative.1 This essentially resolves the classic negative-weight SSSP problem. The previous bounds are O((m+n1.5) log W) [BLNPSSSW FOCS'20] and m4/3+o(1) log W [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic O(m vn log W) bound from over three decades ago [Gabow and Tarjan SICOMP'89].

    Original languageEnglish (US)
    Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
    PublisherIEEE Computer Society
    Pages600-611
    Number of pages12
    ISBN (Electronic)9781665455190
    DOIs
    StatePublished - 2022
    Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
    Duration: Oct 31 2022Nov 3 2022

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    Volume2022-October
    ISSN (Print)0272-5428

    Conference

    Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
    Country/TerritoryUnited States
    CityDenver
    Period10/31/2211/3/22

    Keywords

    • analysis of algorithms
    • graph algorithms
    • graphs and networks
    • path and circuit problems

    ASJC Scopus subject areas

    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Negative-Weight Single-Source Shortest Paths in Near-linear Time'. Together they form a unique fingerprint.

    Cite this