Seminaria - Instytut Informatyki Analitycznej

stycznia 2026

20260115
Poprzedni tydzień
Następny tydzień

Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time

Data: 15.01.2026
Czas rozpoczęcia: 16:45

Andrii Stolitnii

We give a randomized decremental data structure for directed graphs that maintains strongly connected components and single-source reachability under edge deletions in total expected O(m log4 n) update time and O(1) query time (against an oblivious adaptive adversary). The algorithm maintains a multi-level hierarchy of contracted graphs based on a monotone separator chain; when an SCC becomes "large" in an S-distance metric, a small separator is promoted to the next level to split it. Within each SCC it maintains generalized Even–Shiloach trees in the S-distance setting (where the separator acts as a feedback vertex set), and uses random centers plus reuse after splits so each vertex participates in only O(log n) trees in expectation, yielding the near-linear total update bound.

  1. Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen. Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time. STOC 2019. 365-376. (2019).
  2. Shimon Even, Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM. 28, 1-4. (1981).