Solving connectivity problems via basic Linear Algebra

We consider some classical graph connectivity problems like reachability, shortest path and disjoint paths in different settings. For the first two problems, we show efficient parallel algorithms in the dynamic framework, confirming a conjecture of Patnaik and Immerman ’94 for directed reachability. Recently, we have been able to extend this for more general updates. For the shortest disjoint paths problem, we show efficient (and parallel) algorithms in planar graphs where all the terminals lie on a single face. This partly answers an open question of Colin de Verdiere and Schrijver ’08. Interestingly the basic idea behind all these algorithms is to compute some linear algebraic property of the matrix associated with the given graph, which I shall try to convey in this talk. 

Based on joint works with Samir Datta, Raghav Kulkarni, Siddharth Iyer, Thomas Schwentick, and Thomas Zeume.