Efficient Catalytic Graph Algorithms

James Cook, Edward Pyne

We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for $s\to t$ connectivity running…