Talks - Fall 2017

Graph suitable for Kameda's method

Title

Speaker

Date

Time

Venue

Abstract

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.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator