ime-space Tradeoffs for Directed s-t Connectivity

The s-t connectivity problem (STCON), i.e., deciding whether there is a path between two vertices in a directed graph, is a central primitive in graph algorithms and space-bounded complexity. A classical theorem by Savitch shows an O(log^2 n) space algorithm for STCON, but only with super-polynomial time. Whether one can achieve polynomial time within such small space remains a longstanding open question. State-of-the-art polynomial-time algorithms use nearly linear space (Barnes et al.'98), but matching lower bounds for such (''pebbling'' based) techniques form a barrier towards further progress.

 

In this talk, I will present a new randomized polynomial-time algorithm for STCON in the model of catalytic computation. In this model, the algorithm can use an auxiliary full memory having arbitrary initial contents for computation, but needs to restore it to its original contents at the end. Our algorithm matches the frontier for space bounds for polynomial-time algorithms, while using only O(log n) workspace and the rest being borrowed from the auxiliary memory.

 

I will also discuss broader implications of such techniques from catalytic computation for space-bounded complexity, as well as for other fundamental problems such as Edit Distance and Longest Common Subsequence.

 

Joint work with Petr Chmel, Aditi Dudeja, Michal Koucký and Ian Mertz.