PUBLIC VIVA-VOCE NOTIFICATION
3.30 pm,Lecture Hall 803
Static and Dynamic Complexity of Reachability, Matching and Related Problems
Anish Mukherjee
Chennai Mathematical Institute.
28-08-19

---

Abstract

Reachability and Matching are two fundamental graph-theoretic problems that are of prime interest in Algorithms and Complexity Theory. In this thesis, we obtain new complexity upper bounds for these problems both in the static and in the dynamic setting with the primary focus on the parallel complexity of these problems.

In the dynamic model, we design efficient parallel algorithms for Reachability, Distance, and Maximum Matching. Our result for Reachability confirms a long-standing conjecture in dynamic complexity theory [Patnaik and Immerman 1994]. We further generalize these algorithms under batch modifications and also extend the deterministic isolation techniques for these problems in the dynamic setting. In the static environment, the main thrust of the effort is to exploit the structure of planar and other sparse graph classes. We design efficient parallel algorithms for the One-face Shortest k-Disjoint Paths problem that are also sequentially competitive. We further consider the planar Maximum Matching Problem and give pseudo-deterministic NC bound along with designing Logspace approximation schemes.

One of the primary tools that we use here is to employ linear algebraic techniques, re-establishing their usefulness in designing efficient graph algorithms.