Catalytic computation reuses a potentially large in‑use space (catalytic space) that must be restored to its original contents after the computation, while keeping the clean space very small. This enables all problems in (\mathsf{NL}) and even larger classes to be solved in catalytic logspace [Buhrman et al., STOC2014].
In [Chmel et al., CCC2026] the catalytic space for reachability was restricted to sublinear space, specifically $n / 2^{\theta(\sqrt{\log n})}$, while still running in polynomial time. This matches the non‑catalytic bounds from [Barnes et al., SICOMP1998].
We extend that reachability bound to shortest‑distance, proving a simultaneous sublinear catalytic space and polynomial‑time bound (hereafter called sublinear (\mathsf{CLP})). This is the first result that achieves sublinear space and polynomial time for distance even without the catalytic discipline. Moreover, our bound works for graphs whose edge weights are polynomially bounded.
Along the way we show that the determinant can be computed in near‑linear catalytic space $\mathcal{O}(n\log^{O(1)}{n})$ and polynomial time. We also present applications to planar matching problems.
Our starting point was the catalytic computation of reachability in directed graphs by [Cook‑Pyne, ITCS2026]. [Edenhofer, arXiv:2602.21088] used it to trade off catalytic and non‑catalytic space, while [Chmel et al., CCC2026] compressed the graph while preserving $s,t$‑reachability to achieve a smaller space bound. All three approaches can be adapted to yield an algorithm for unweighted distance.
Our main contribution is to define an approximation to the walk polynomial in weighted graphs that allows us to infer weighted $s,t$‑distance within sublinear (\mathsf{CLP}). This is achieved by non‑trivially combining elements from each of the three cited works.
Review