Efficient Catalytic Graph Algorithms This paper subsumes a manuscript by the first author which showed how to simulate random walks on acyclic graphs [ Coo25 ] .
James Cook [email protected], Edward Pyne [email protected] · 2025
Read Efficient Catalytic Graph Algorithms This paper subsumes a manuscript by the first author which showed how to simulate random walks on acyclic graphs [ Coo25 ] . by James Cook [email protected], Edward Pyne [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06209.txt.
Introduction
Borrowed workspace that must be returned untouched is the strange resource of catalytic computing, and James Cook and Edward Pyne give it fast graph algorithms in a 2025 paper. Catalytic logspace lets an algorithm use a large memory filled with any data, provided it restores the contents exactly. Earlier work in this model lacked stated running times.
Their randomized algorithm settles s-t connectivity by pushing values along edges, one register per vertex; a non-random version runs slower but surely. A second algorithm simulates random walks, estimating where a walk ends within a set error by counting visits per vertex. Both carry concrete polynomial runtimes, making catalytic methods practical rather than mere theory.
Catalog record
| CREATOR | James Cook [email protected], Edward Pyne [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06209
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Catalytic Graph Algorithms This paper subsumes a manuscript by the first author which showed how to simulate random walks on acyclic graphs [ Coo25 ] . James Cook [email protected], Edward Pyne [email protected] Abstract We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for s → t s\to t connectivity running in O ~ ( n m ) \widetilde{O}(nm) time, and a deterministic catalytic algorithm for the same running in O ~ ( n 3 m ) \widetilde{O}(n^{3}m) time. The former algorithm is the first algorithmic use of randomization in 𝖢𝖫 \mathsf{CL} . The algorithm uses one register per vertex and repeatedly “pushes” values along the edges in the graph. Second, a deterministic catalytic algorithm for simulating random walks which in O ~ ( m T 2 / ε ) \widetilde{O}(mT^{2}/\varepsilon) time estimates the probability a T T -step random walk ends at a given vertex within ε \varepsilon additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges. Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in n n . \tau_{0}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0.7,0.35,0}\tau_{1}} {\color[rgb]{0,0.3,0}\tau_{2}} {\color[rgb]{0,0,1}\tau_{3}} {\color[rgb]{0.75,0,0.25}\tau_{4}} s t \Rightarrow \tau_{0}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0.7,0.35,0}\tau_{1}} {\color[rgb]{0,0.3,0}\tau_{2}}+\tau_{0}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0,0,1}\tau_{3}}+\tau_{0}+{\color[rgb]{0.7,0.35,0}\tau_{1}}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0.75,0,0.25}\tau_{4}}+2\tau_{0}+{\color[rgb]{0.7,0.35,0}\tau_{1}}+{\color[rgb]{0,0.3,0}\tau_{2}}{\color[rgb]{1,0,0}\mathbf{+2}} s t \tau_{0}{\color[rgb]{1,0,0}\mathbf{+1}} \tau_{0}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0.7,0.35,0}\tau_{1}} \tau_{0}+{\color[rgb]{0,0.3,0}\tau_{2}}{\color[rgb]{1,0,0}\mathbf{+1}} {\color[rgb]{0,0,1}\tau_{3}}+\tau_{0}+{\color[rgb]{0.7,0.35,0}\tau_{1}}{\color[rgb]{1,0,0}\mathbf{+1}} Detecting s\to t paths by adding values along edges: a change ( +1 ) to s reaches t . \boldsymbol{\uparrow} \boldsymbol{\downarrow} \uparrow \downarrow \boldsymbol{\uparrow} \downarrow \boldsymbol{\downarrow} \uparrow \boldsymbol{\uparrow} \downarrow \boldsymbol{\downarrow} \downarrow \boldsymbol{\uparrow} \boldsymbol{\uparrow} \downarrow \boldsymbol{\downarrow} \uparrow \downarrow Simulating a random walk, using one bit per node to alternate between random choices. 1 Introduction 1.1 Catalytic space In the catalytic space model, an algorithm has two tapes to use as memory: a smaller ordinary tape, and a larger “catalytic” tape which starts out filled with arbitrary data. The algorithm may freely write to and read from both tapes, but when it finishes, the catalytic tape’s original content must be restored. Often the working tape has size O(\log n) and the catalytic tape has size \Poly(n) , defining the decision class catalytic logspace or \mathsf{CL} . Buhrman, Cleve, Koucký, Loff and Speelman [ BCK+14 ] initiated the study of this model with their surprising result that evaluation of logarithmic depth threshold circuits was possible in \mathsf{CL} , from which it follows for example that s\rightarrow t connectivity and estimation of random walks (the complete problems for nondeterministic logspace ( \NL ) and randomized logspace ( \mathsf{BPL} ) respectively) are in \mathsf{CL} . Broadly speaking, two ways to take advantage of catalytic space have been explored previously: compression-based techniques are able to make use of incompressible catalytic tapes (as randomness, for example); and algebra-based techniques treat the tape as an array of registers which they use to execute a “straight-line program”, a pre-determined sequence of mathematical operations. The original \TC^{1}\subseteq\mathsf{CL} result is an example of the algebraic approach. The compression-based approach began with a “compress-or-random” argument that \mathsf{BPL}\subseteq\mathsf{CL} (Mertz [ Mer23 ] gives a sketch of it). Several subsequent works [ DPT24 , Pyn24 , CLMP24 , KMPS25 ] applied this technique further, with Cook, Li, Mertz and Pyne [ CLMP24 ] using it to derandomize randomized \mathsf{CL} itself. All of these results in both branches have a “complexity” flavor --- in particular, the runtime for the relevant problem is some large polynomial. 1 1 1 Cook [ Coo ] implemented a register program for s\rightarrow t connectivity with an estimated runtime of \Theta(n^{8}) , and catalytic tape size \Theta(n^{3}\log n) . We give new techniques for deciding graph connectivity and estimating random walks. Our algorithms are very simple and implementable, and allow a precise analysis of the catalytic space consumption and runtime. 2 2 2 For the runtime bounds, we assume we have RAM access to the catalytic tape and oracle access to the graph. This does not affect the structure of the class (as we can simulate a catalytic RAM with a standard catalytic machine with a polynomial slowdown). We hope this will initiate the study of \mathsf{CL} from an algorithmic perspective. 1.2 Our Results: Connectivity We first state our results for connectivity, beginning with our deterministic algorithm: Theorem 1 . There is a catalytic algorithm that, given a simple directed graph with n vertices and m edges together with vertices s,t , decides whether there exists a path from s to t . The algorithm uses O(\log n) workspace and \widetilde{O}(n^{2}) catalytic space, and runs in time \widetilde{O}(n^{3}m) . Next, we give a randomized algorithm that improves the runtime to \widetilde{O}(nm) and space usage to \widetilde{O}(n) , only a factor of n in runtime from the linear-workspace BFS algorithm: Theorem 2 . There is a randomized catalytic algorithm 3 3 3 The algorithm always resets the catalytic tape no matter the random coins. If there is no s\rightarrow t path, the algorithm always returns no, and if there is an s\rightarrow t path returns yes with probability at least 1/2 . that, given a simple directed graph with n vertices and m\geq n edges together with vertices s,t , decides whether there exists a path from s to t . The algorithm uses O(\log n) workspace and \widetilde{O}(n) catalytic space, and runs in time \widetilde{O}(nm) . As far as we know, this result is the first use for randomness in catalytic computing — rather than using it to place a new problem in the class (now provably impossible [ CLMP24 ] ), we use it to give an algorithmic speedup. Remark 3 . Under conjectured time-space tradeoffs for connectivity, the catalytic space usage of Theorem 2 is optimal up to polylogarithmic factors, even for an algorithm running in arbitrarily large polynomial time. 4 4 4 It can be shown that a randomized catalytic logspace algorithm for s\rightarrow t connectivity using n^{1-\varepsilon} catalytic space would imply a randomized n^{1-\varepsilon} space, polynomial-time algorithm for s\rightarrow t connectivity, which has been open for decades [ Wig92 ] and has been conjectured not to exist. In fact, we can obtain an additional desirable property. The practical motivation for \mathsf{CL} is to borrow temporarily unused space to perform useful computation. Unfortunately, if any part of the borrowed section of memory is needed during the computation of the catalytic machine, the original owner may need to wait for the entire catalytic computation to finish. As such, existing catalytic algorithms do not seem to permit sharing a single section of memory without huge latency. 5 5 5 Alongside the large runtime of prior algorithms, this was mentioned as the primary issue for practical catalytic computing by Cook [ Coo ] . To rectify this problem, we define a notion of catalytic algorithms that must permit fast query access to the original memory configuration at all times: Definition 4 . A catalytic algorithm A is locally revertible in time t if at any point during the execution of A with initial tape \tau , the algorithm can be paused and queried on an index i , and will return \tau_{i} in time t (and then continue its execution). We show that (at the cost of polynomially more catalytic space) our