#### Simultaneous Timespace Bounds for the Graph Reachability Problem

#### Rahul Jain

#### 14th June, 2017

#### 4pm

#### KD103

#### The graph reachability problem is the problem of checking if a path exists between two fixed vertices in a given graph. This problem is complete for the class nondeterministic logspace (NL). Hence understanding its complexity would give us a better understanding of the class NL. Standard graph traversal algorithms like BFS and DFS can solve this problem in linear time. However, they require linear space as well. We also have an algorithm due to Savitch which requires only $O(\log^2 n)$-space. However, it takes quasi-polynomial time.
Widgerson asked if it is possible to design a polynomial time algorithm for this problem that uses only $O(n^{\epsilon})$ space, for some constant $\epsilon < 1$. In this talk, we will discuss various progress made on this question.

We look at several approaches that tries to reduce the space complexity while maintaining the polynomial time bound. We start with the BBRS algorithm which requires $n/2^{O(\sqrt{\log n})}$-space for general graphs. This would be followed by discussion on $O(n^{1/2 + \epsilon})$-space algorithm for planar graphs and then finally an $O(n^\epsilon)$-space algorithm for layered planar graph, where $\epsilon$ can be an arbitrarily small constant. All these algorithms run simultaneously in polynomial time.