We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only 𝒪(log(n)) workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed s-t connectivity using n / 2^{Θ(√{log n})} catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [James Cook and Edward Pyne, 2026]. Furthermore, using only 𝒪(log(n)) random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using n / 2^{Θ(√{log n})} catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].