PhD defence by Maximilian Probst Gutenberg

Title

Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs.

Abstract

In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions:

• Single-Source Reachability (SSR): given a distinct source vertex r in a graph, the objective is to maintain the set of vertices that r can reach throughout the entire update sequence.
• Strongly-Connected Components (SCC): the goal is to maintain a partition of the vertex set such that every two vertices in the same partition set X are on a common cycle, while no two vertices across different partition sets are.
• Single-Source Shortest Paths (SSSP): given a dedicated source vertex s, the objective is to maintain the distance from s to every other vertex in the graph.

These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts. Our techniques lead to the first near-optimal data structures for these problems in various different settings.

In particular, we obtain

• the first randomized data structure to maintain SSR and SCCs in near-optimal total update time in a graph undergoing edge deletions.
• the first randomized data structure to maintain SSSP in partially dynamic graphs in near-optimal update time for dense graphs.
• the first deterministic data structures for SSR and SCC for graphs undergoing edge deletions, and for SSSP in partially dynamic graphs that improve upon the O(mn) total update time by Even and Shiloach from 1981 that is often considered a fundamental barrier.

Assessment Committee

Chairperson: Associate professor, Jakob Nordström, Department of Computer Science, UCPH
Professor, Valerie King, University of Victoria
Professor, Uri Zwick, University of Tel Aviv

Academic supervisors

Associate professor, Christian Wulff-Nilsen, Department of Computer Science, University of Copenhagen
Professor, Mikkel Thorup, Department of Computer Science, University of Copenhagen

Moderator at this defence will be:
Professor, Jon Sporring, Department of Computer Science, University of Copenhagen

For an electronic copy of the thesis, please contact phdadmin@di.ku.dk