# Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, where m is the number of edges and n is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m = \Theta(n^{1.5}) the running time is O(n^{2.47}), just barely below mn = \Theta(n^{2.5}). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of \tilde O(min( m^{7/6} n^{2/3}, m^{3/4} n^{5/4 + o(1)}, m^{2/3} n^{4/3+o(1)} + m^{3/7} n^{12/7+o(1)})). This gives, e.g., O(n^{2.36}) for the notorious case m = \Theta(n^{1.5}). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.

Top Category | Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings) |

Event Title | 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) |

Divisions | Theory and Applications of Algorithms |

Subjects | Datenstrukturen Theoretische Informatik |

Event Location | Kyoto, Japan |

Event Type | Conference |

Event Dates | July 6â€“10, 2015 |

Date | July 2015 |

Export |