Complexity seminar

Solving connectivity problems via basic Linear Algebra

Anish Mukherjee

MFF UK

Friday, 4. October 2019 - 13:30 to 15:00

in IM, rear building, ground floor

We consider some classical graph connectivity problems like reachability,

shortest path and disjoint paths in this talk. For the first two problems,

we show efficient parallel (dynamic AC^0) algorithms in the dynamic model,

confirming a conjecture of Patnaik and Immerman ’94 for directed

reachability. Recently, we have been able to extend this for batch updates

also. For the optimization version of the disjoint paths problem, we show

efficient sequential and parallel algorithms in planar graphs where all the

terminals lie on a single face. This partly answers an open question of

Colin De Verdière and Schrijver ’08. Interestingly the basic idea behind

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.

shortest path and disjoint paths in this talk. For the first two problems,

we show efficient parallel (dynamic AC^0) algorithms in the dynamic model,

confirming a conjecture of Patnaik and Immerman ’94 for directed

reachability. Recently, we have been able to extend this for batch updates

also. For the optimization version of the disjoint paths problem, we show

efficient sequential and parallel algorithms in planar graphs where all the

terminals lie on a single face. This partly answers an open question of

Colin De Verdière and Schrijver ’08. Interestingly the basic idea behind

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.