On some Recent Dynamic Graph Algorithms

Abstract: We discuss some recent algorithms for problems in dynamic graphs undergoing edge insertions and deletions. In the first part of the talk, we will discuss connections between the approximate bipartite matching problem in fully dynamic graphs, and versions of the online matrix-vector multiplication conjecture. These connections will lead to faster algorithms in online and offline settings, as well as some conditional lower bounds.

In the second part of the talk, we will briefly discuss how interior point methods can be used to design algorithms for partially dynamic graphs: those undergoing only edge insertions (incremental) or only edge deletions (decremental). This leads to almost-optimal algorithms for problems including incremental cycle detection, and decremental s-t distance.