Nikos Parotsidis: Decremental Single-Source Reachability and Strongly Connected Components

Data dell'evento: 
Wednesday, 8 November, 2017 - 12:00
Room A4@DIAG, via Ariosto 25, ground floor
Nikos Parotsidis, University of Rome Tor Vergata
We present randomized algorithms with a total update time of O~(m \sqrt{n}) for the problems of decremental single-source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler. In this talk, we are going to briefly review the Las Vegas algorithm by Roditty and Zwick [SICOMP 08] and the algorithm by Łącki [TALG 13], both with a total update time O(mn) (expected time in the case of the algorithm by Roditty and Zwick). Our algorithms carefully combine these two results, along with new structural properties, including a separation lemma in the case of graphs with a large diameter.

(Appeared in FOCS 2016. Joint work with Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, and Jakub Łącki.)