Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs

Peng, Pan; Wang, Yuyang

doi:10.4230/LIPIcs.ICALP.2026.147

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs

Pan Peng

School of Computer Science and Technology, University of Science and Technology of China, Hefei, China Yuyang Wang

School of Computer Science and Technology, University of Science and Technology of China, Hefei, China

Abstract

We study local computation algorithms (LCAs) for constructing spanning trees. In this setting, the goal is to determine locally, for each edge $e\in E$ , whether it belongs to a spanning tree $T$ of the input graph $G$ , where $T$ is defined implicitly by $G$ and the randomness of the algorithm. It is known that sublinear-probe LCAs for spanning trees do not exist in general graphs, even for simple graph families. We identify a natural and well-studied class of graphs – expander graphs – that do admit sublinear-time LCAs for spanning trees. This is perhaps surprising, as previous work on expanders only succeeded in designing LCAs for sparse spanning subgraphs, rather than full spanning trees. We design an LCA with probe complexity $O\left(\sqrt{n}\left(\frac{\log^{2}n}{\phi^{2}}+d\right)\right)$ for graphs with conductance at least $\phi$ and maximum degree at most $d$ (not necessarily constant), which is nearly optimal when $\phi$ and $d$ are constants, since $\Omega(\sqrt{n})$ probes are necessary even for expanders. Next, we show that for the natural class of Erdős-Rényi graphs $G(n,p)$ with $np=n^{\delta}$ for any constant $\delta>0$ (which are expanders with high probability), the $\sqrt{n}$ lower bound can be bypassed. Specifically, we give an average-case LCA for such graphs with probe complexity $\tilde{O}(\sqrt{n^{1-\delta}})$ .

Finally, we extend our techniques to design LCAs for the minimum spanning tree (MST) problem on weighted expander graphs. Specifically, given a $d$ -regular unweighted graph $\bar{G}$ with sufficiently strong expansion, we consider the weighted graph $G$ obtained by assigning to each edge an independent and uniform random weight from $\{1,\ldots,W\}$ , where $W\leq d/2$ and $W=o(\log n)$ . We show that there exists an LCA that is consistent with an exact MST of $G$ , with probe complexity $\tilde{O}(\sqrt{n}d^{2})$ .

Keywords and phrases:

Local Computation Algorithms, (Minimum) Spanning Trees, Expander Graphs, Random Graphs

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Streaming, sublinear and near linear time algorithms ; Theory of computation

\rightarrow

Graph algorithms analysis ; Mathematics of computing

\rightarrow

Graph algorithms

Related Version:

Full Version: https://arxiv.org/abs/2602.07394 [46]

Funding:

Supported in part by NSFC Grant 62272431 and Quantum Science and Technology – National Science and Technology Major Project (Grant No. 2021ZD0302901).

DOI:

10.4230/LIPIcs.ICALP.2026.147

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Constructing a spanning tree is a fundamental problem in computer science and graph theory. In this paper, we study local computation algorithms (LCAs) for constructing spanning trees. In this setting, the goal is to determine quickly whether a given edge $e$ belongs to some spanning tree, without computing the entire tree. Instead, the algorithm only accesses the local neighborhood of $e$ via probes¹¹1Some works refer to query access to the graph. In our setting, however, since the algorithm is designed to answer queries, we reserve the term query for inputs to the LCA. to the graph. The key challenge is consistency: ensuring that answers to all edge queries are consistent with the same underlying spanning tree. Such LCAs are useful in scenarios where we do not need the full solution at once, or where multiple independent processes may wish to query edges in parallel.

The LCA model (also known as the centralized local model) was introduced by Rubinfeld et al. [47] and Alon et al. [2]. It generalizes earlier frameworks, including graph property testing and sublinear-time algorithms for approximating graph parameters. All these models share a common motivation: inferring global properties of a graph while exploring only a small portion of the input through local probes. While property testing and approximation algorithms typically deal with large input and small output (e.g., estimating a global quantity or deciding a property), LCAs handle the more demanding large input and large output regime, where the goal is to construct a global structure, such as a spanning tree, locally and consistently on demand.

The study of LCAs with sublinear probe complexity for spanning trees was initiated by Levi et al. [40, 41] nearly a decade ago. They quickly identified a fundamental limitation: it is impossible to design a sublinear-time LCA for constructing spanning trees, even for very simple graph families! For example, consider a path and a cycle, both of length $n$ . In the path, every edge must be included in the spanning tree, while in the cycle, at least one edge must be omitted to break the cycle. Distinguishing between these two cases requires probing a linear number of edges, violating the sublinear-probe constraint of LCAs.

The above observation motivated a shift in focus toward LCAs for sparse spanning subgraphs – connected subgraphs that span all vertices and contain at most $(1+\varepsilon)n$ edges, for some small $\varepsilon>0$ . This relaxation permits sublinear probe complexity while still yielding meaningful global structures. Several works have since proposed LCAs for sparse spanning subgraphs in different graph families (see, e.g., [40, 41, 39, 43, 38, 37]). For example, in planar graphs, LCAs with $\mathrm{poly}(1/\varepsilon)$ probe complexity are known [41]; in bounded-degree expander and well-clusterable graphs, LCAs with $\tilde{O}(\sqrt{n})$ probe complexity exist [37]; and in general graphs with maximum degree at most $d$ , LCAs with $\tilde{O}(n^{2/3}\cdot\mathrm{poly}(d/\varepsilon))$ probe complexity are available [36], with a known lower bound of $\Omega(\sqrt{n})$ [40]. [40] studied LCAs for computing minimum-weight spanning subgraph in minor-free graphs, achieving a $(1+\varepsilon)$ -approximation to the optimal weight (the weight of a minimum spanning tree), with probe complexity quasi-polynomial in $1/\varepsilon$ , $d$ , and $W$ .

In this work, we identify a natural and well-studied class of graphs – expander graphs – that do admit sublinear-time LCAs for constructing spanning trees. This is perhaps surprising, given that prior works have also studied expander graphs (e.g., [41, 37]), yet all of them were only able to design LCAs for sparse spanning subgraphs, rather than full spanning trees. On the other hand, the cycle-versus-path example discussed earlier only rules out sublinear LCAs on graphs with poor expansion (i.e., tree-like structures), but does not apply to well-connected graphs. We achieve nearly optimal probe complexity for our LCA on expander graphs. We further focus on a specific subclass of expander graphs, namely Erdős-Rényi graphs, and design even faster average-case LCAs for constructing spanning trees in these settings, thereby bypassing the worst-case lower bounds that hold for general expanders. Finally, we extend our techniques to obtain an LCA for constructing an exact minimum spanning tree (MST) on certain weighted expander graphs, where edge weights are chosen independently and uniformly at random from the set $[W]:=\{1,\ldots,W\}$ for some integer $W$ .

1.1 Basic Definitions

To formally describe our results, we first introduce some basic definitions. We have the following definition of LCA for a graph problem.

Definition 1.1 (Local Computation Algorithm).

A Local Computation Algorithm (LCA) for a problem $\Pi$ is an oracle algorithm $\mathcal{A}$ that answers a problem-specific type of query about a solution $X$ to $\Pi$ on input graph $G$ , satisfying the following properties:

$\blacksquare$

$\mathcal{A}$ uses only probe access to $G$ , a sequence of random bits $R$ , and local workspace to respond to any admissible query $q$ to $X$ .
$\blacksquare$

The random string $R$ is sampled once and fixed for the entire sequence of queries, while the local workspace, including the current query and response, is erased after each query.
$\blacksquare$

Answers to any sequence of queries returned by $\mathcal{A}$ must be consistent with $X$ .

Let $T_{\mathcal{A}}(G,q)$ denote the expected (over the choice of the random bits $R$ ) number of probes it takes for the LCA $\mathcal{A}$ to answer query $q$ on input graph $G$ , and set $T_{\mathcal{A}}(G)=\max_{q}T_{\mathcal{A}}(G,q)$ . We say the LCA has (worst-case) probe complexity $T(n)$ if the maximum of $T_{\mathcal{A}}(G)$ over all possible $n$ -vertex input graphs $G$ is $T(n)$ .

When specialized for spanning trees, we have the following definition.

Definition 1.2 (LCA for (Minimum) Spanning Tree).

An algorithm $\mathcal{A}$ is a Local Computation Algorithm for (Minimum) Spanning Tree if for input graph $G$ , $\mathcal{A}$ is an LCA answering edge-membership query to a subgraph $T$ of $G$ , such that $T$ is a (minimum) spanning tree with probability at least $\frac{2}{3}$ .

Here “edge-membership query to $T$ ” means that on input $(u,v)\in E(G)$ , $\mathcal{A}$ returns whether $(u,v)\in E(T)$ .

Beyond the worst-case LCA, recently, the average-case LCA has also been introduced. These are LCAs whose input graph is from a random graph family. In [10], the authors define a new scheme of local computation algorithm called “average-case LCA”, assuming that the input graph is drawn from some distribution and asks the LCA to succeed with probability at least $1-\frac{1}{n}$ over a random graph from this distribution.

Definition 1.3 (Average-case LCA).

We say that $\mathcal{A}$ is an Average-Case Local Computation Algorithm for a distribution $\mathcal{G}$ over objects of size $n$ for a problem $\Pi$ if, with probability at least $1-1/n$ over the random draw $G\sim\mathcal{G}$ , the algorithm $\mathcal{A}^{G}$ (which has probe access to the input $G$ ) satisfies the requirements of an LCA.

We say that $\mathcal{A}$ has average-case probe complexity $T(n)$ if the expected number of probes $T_{\mathcal{A}}(G)$ over $G\sim\mathcal{G}$ is at most $T(n)$ . Similarly, $\mathcal{A}$ has worst-case probe complexity $T(n)$ if the maximum number of probes $T_{\mathcal{A}}(G)$ over $G\sim\mathcal{G}$ is at most $T(n)$ .

1.2 Our Results

Now we state our main results. Let $G=(V,E)$ be a graph with $n$ vertices and maximum degree at most $d$ (called a $d$ -bounded graph), for $d\geq 3$ . Let $S\subseteq V$ be a vertex set. The conductance of $S$ is defined as $\phi_{G}(S):=\frac{|E(S,V\setminus S)|}{\mu_{G}(S)}$ , where $E(S,V\setminus S)$ is the set of edges between $S$ and $V\setminus S$ and $\mu_{G}(S):=\sum_{v\in S}deg(v)$ is the total degree of vertices in $S$ . The conductance of $G$ is defined to be $\phi_{G}:=\min\limits_{\begin{subarray}{c}\emptyset\subsetneq S\subseteq V\\ \mu_{G}(S)\leq\mu_{G}(V)/2\end{subarray}}\phi_{G}(S)$ . We informally say that $G$ is an expander when $\phi_{G}$ is bounded from below by a constant.

Spanning Trees in Expanders

For a graph $G$ with conductance at least $\phi$ and maximum degree at most $d$ , we give an LCA that provides local access to a spanning tree of $G$ with low stretch. For $G=(V,E)$ , a subgraph $H$ is called a $k$ -spanner of $G$ if $\mathrm{dist}_{H}(u,v)\leq k\cdot\mathrm{dist}_{G}(u,v)$ for any vertices $u,v\in V$ , where $\mathrm{dist}_{G}(u,v)$ (resp. $\mathrm{dist}_{H}(u,v)$ ) is the distance between $u$ and $v$ in graph $G$ (resp. $H$ ). We refer to $k$ as the stretch factor.

Theorem 1.4.

Given adjacency-list probe access to a $d$ -bounded connected graph $G=(V,E)$ and a lower bound $\phi$ on the conductance of $G$ , there is an LCA that answers edge-membership queries to a subgraph $T=(V,E^{\prime})$ of $G$ such that $T$ is a spanning tree with probability at least $(1-\frac{1}{n})$ . Additionally, $T$ has depth $O(\frac{\log n}{\phi^{2}})$ , which implies that $T$ is also a $O(\frac{\log n}{\phi^{2}})$ -spanner. The LCA has probe complexity $O(\sqrt{n}(\frac{\log^{2}n}{\phi^{2}}+d))$ .

The above result can be contrasted with the recent work of Levi et al. [37], who designed a local computation algorithm (LCA) for expander graphs with conductance at least $\phi$ . Their algorithm maintains a subgraph with $n+O\left(\frac{\sqrt{n}\log^{2}n}{\phi^{2}}\right)$ edges, achieves probe complexity $O\left(\sqrt{n}\cdot\left(\frac{\log^{2}n}{\phi^{2}}+d^{2}\right)\right)$ , and guarantees a stretch factor of $O\left(\frac{\log n}{\phi^{2}}\right)$ . In comparison, our algorithm maintains a spanning tree (with exactly $n-1$ edges) and achieves lower probe complexity, thereby yielding a strict improvement over their result. Moreover, we note that the probe complexity of our LCA is nearly optimal for graphs with polylogarithmic maximum degree. In particular, a lower bound of $\Omega(\sqrt{n})$ probes is known for LCAs that compute sparse spanning subgraphs in bounded-degree expander graphs [40].

Spanning Trees in Erdős-Rényi Graphs

Now that we have an LCA for spanning trees with nearly optimal probe complexity on worst-case expanders, a natural question is to ask: Can we go beyond worst-case expanders and achieve even better probe complexity?

To address this question, we adopt the framework developed by Biswas et al. [10] for analyzing local computation algorithms over large random objects. In particular, we provide an answer in the setting where the input graph $G$ is drawn from the Erdős-Rényi distribution. In the Erdős-Rényi graph with parameters $n, p$ such that $p\in(0,1]$ , a graph $G=([n],E)$ is generated from $G(n,p)$ , denoted $G\sim G(n,p)$ , by including each edge $(u,v)$ independently with probability $p$ for every distinct pair $u,v\in[n]$ .

Theorem 1.5.

For $np=n^{\delta}$ with any constant $\delta\in(0,1]$ and a graph $G\sim G(n,p)$ , given access to $G$ in the general graph model, there exists an average-case LCA with probe complexity²²2For simplicity, we focus on the average-case probe complexity. With a suitable cap on the number of probes and minor adaptations of the analysis, the same bound can be achieved in the worst case. $\tilde{O}(\sqrt{n^{1-\delta}})$ that, with probability at least $1-\frac{1}{n}$ , supports edge-membership queries to a spanning tree of $G$ .

Note that the probe complexity $\tilde{O}(\sqrt{n^{1-\delta}})$ strictly improves upon the $\Omega(\sqrt{n})$ lower bound for worst-case instances. As $\boldsymbol{\delta\to 0}$ , the random graph $G\sim G(n,p)$ approaches the behavior of a bounded-degree expander. In this regime, the probe complexity $\tilde{O}(\sqrt{n^{1-\delta}})$ converges to $\tilde{O}(\sqrt{n})$ , nearly matching the complexity of our LCA for bounded-degree expanders established in Theorem 1.4.

On the other hand, as $\boldsymbol{\delta\to 1}$ , the graph $G\sim G(n,p)$ becomes increasingly dense and approaches a complete graph. Intuitively, in this case, much more efficient LCAs are possible. For example, suppose $np=\Omega(n/\log n)$ . We can then sample a subset $S\subseteq V$ of size $\Theta(\log^{2}n)$ such that, with high probability³³3Unless stated otherwise, “with high probability” (w.h.p.) means that the probability tends to $1$ as $n\to\infty$ ., the induced subgraph $G[S]$ is connected. A spanning tree $T_{0}$ of $G[S]$ can be computed. Furthermore, for each remaining vertex $u\in V\setminus S$ , the choice of $p$ and the size of $S$ ensure that $u$ has at least one neighbor in $S$ with high probability. We can then connect $u$ to the lexicographically smallest such neighbor $v\in S$ by adding the edge $(u,v)$ to $T_{0}$ . This construction yields a spanning tree of $G$ and can be simulated by an LCA with probe complexity $\mathrm{poly}(\log n)$ . This phenomenon is consistent with the behavior of our algorithm, as the probe complexity $\tilde{O}(\sqrt{n^{1-\delta}})$ tends toward $\tilde{O}(1)$ when $\delta\to 1$ .

Minimum Spanning Tree

Having established an LCA for spanning trees on expander graphs, we now extend our techniques to the minimum spanning tree (MST) problem. We call a graph $G$ an $(n,d,\lambda)$ -graph if $G$ is a $d$ -regular graph on $n$ vertices whose adjacency matrix has eigenvalues

d=\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}

and satisfies $\lambda=\max\{\lambda_{2},|\lambda_{n}|\}$ . Building on Theorem 1.4 as a subroutine, we design the following LCA for computing an MST on $(n,d,\lambda)$ -graphs.

Theorem 1.6.

Given adjacency-list probe access to a weighted graph $G=(V,E,\textbf{w})$ such that the underlying unweighted graph $\bar{G}=(V,E)$ is an $(n,d,\lambda)$ -graph with $d=\omega_{n}(1)$ and $\lambda=o(d)$ , and assuming that the weight function w assigns to each edge $e\in E$ an independent weight drawn uniformly from $\{1,2,\ldots,W\}$ , where $W\leq d/2$ and $W=o(\log n)$ , then with high probability there exists an LCA for the minimum spanning tree of $G$ with probe complexity $\tilde{O}(\sqrt{n}\,d^{2})$ .

We remark that Theorem 1.6 holds for any slowly growing function $d=d(n)$ , for example $d=\log n$ . Moreover, since the underlying graph $\bar{G}$ is $d$ -regular and satisfies $\lambda=o(d)$ , Cheeger’s inequality implies that $\bar{G}$ has constant conductance, i.e., $\phi_{\bar{G}}=\Omega(1)$ , and is therefore an expander.

To the best of our knowledge, Theorem 1.6 is the first non-trivial LCA for constructing an exact minimum spanning tree on a natural class of weighted graphs, albeit under random edge weights. The assumption of uniformly distributed weights is made primarily for clarity of presentation. In the full version of this paper [46], we show that the result extends to general distributions over $\{1,\ldots,W\}$ satisfying a suitable non-criticality condition.

We further observe that without the random edge-weight assumption, i.e., when edge weights are assigned adversarially, it is impossible to obtain an LCA with sublinear probe complexity, even when $W=2$ and the underlying graph is an expander; see the full version of this paper [46]. Finally, note that when $W=1$ , the MST problem reduces to the spanning tree problem, for which an $\Omega(\sqrt{n})$ lower bound on the probe complexity of LCAs is known [40].

1.3 Technical Overview

Now we provide an overview of the techniques used in the design and analysis of our LCAs.

1.3.1 Spanning Tree in Expander Graphs

Our local algorithm is based on a local implementation of a carefully designed global spanning tree algorithm. The global algorithm leverages both the spectral properties of random walks on expanders and the structural properties of shortest paths in the graph. A key aspect of our approach is ensuring that the global algorithm can be efficiently simulated locally, which we achieve through a detailed analysis of its behavior. We note that the recent work of [37] on LCAs for sparse spanning subgraphs also relies on a global algorithm guided by random walks. However, in one crucial subroutine, their approach constructs spanning forests using Voronoi cells, whereas our method is fundamentally based on shortest-path structures. We first sketch our global algorithm on an expander graph $G=(V,E)$ .

Global Algorithm Overview

The global algorithm proceeds in three Phases. It begins by selecting an arbitrary vertex $s$ , which then serves as both the root of the spanning tree and the seed for the random walks.

In Phase 1, starting from vertex $s$ , the algorithm initiates $\tilde{\Theta}(\sqrt{n})$ lazy random walks, each of length $\tau$ , where $\tau$ denotes the mixing time of the graph. During these walks, the algorithm faithfully records the full trajectory of each walk, including every vertex visited and every edge traversed. We denote the set of vertices by $S$ , and the set of edges by $H$ .

Since the vertices in $S$ and edges in $H$ are generated by random walks of length $\tau$ , the graph $G_{0}=(S,H)$ forms a spanning subgraph of $G$ with diameter at most $2\tau$ . Moreover, $G_{0}$ is fully explicit to the algorithm, allowing it to access any information about $G_{0}$ without issuing any new probes.

In Phase 2, the algorithm performs a BFS from the root $s$ in the graph $G_{0}$ to construct a BFS tree of $G_{0}$ . Since $G_{0}$ is fully explicit, this phase does not require any probes. We denote the resulting tree by $T_{0}=(S,E^{\prime})$ , and refer to it as the core tree. Since the diameter of $G_{0}$ is at most $2\tau$ , the diameter of the core tree $T_{0}$ is also bounded by $2\tau$ .

In Phase 3, we connect each vertex $u\notin S$ to the core tree $T_{0}$ , where all vertices in $S$ already lie on a spanning tree rooted at $s$ . For each such vertex $u$ , the algorithm identifies its anchor – the closest vertex to $u$ in $S$ . A key distinction from prior work [37] lies in how ties are broken when multiple candidate vertices in $S$ are equally close to $u$ : rather than selecting the anchor based on vertex ID, we break ties using the lexicographical order of the paths from $u$ to the candidates in $S$ . In other words, the anchor of $u$ is the vertex in $S$ for which the shortest path from $u$ is lexicographically minimal among all such paths. This structural property of the anchor plays a crucial role in improving both the probe complexity and the total number of edges in the resulting subgraph.

Figure 1: Illustration of the global spanning-tree construction.

Specifically, the algorithm iterates over every vertex $u\in V\setminus S$ . For each such vertex $u$ , the algorithm performs a BFS⁴⁴4This is implemented as the subroutine FindPath in our algorithm. starting from $u$ to discover the path to its anchor. Once the path is found, the algorithm updates the edge set $E^{\prime}$ by including all edges along the path (while keeping the set $S$ invariant). After all iterations are complete, $E^{\prime}$ contains a path from the root $s$ to every vertex $u\in V$ , where each path consists of two segments:

1.

a path from $s$ to the anchor of $u$ along the core tree $T_{0}$ ;
2.

a path from the anchor to $u$ discovered during the iteration over $u$ .

Therefore, after Phase 3, the subgraph $T=(V,E^{\prime})$ forms a connected spanning subgraph of $G$ . Moreover, the first segment has length at most $2\tau$ as discussed before, and the second segment has length at most the diameter of the graph, which is also bounded by $\tau$ (shown in the proof).

Having established that $T=(V,E^{\prime})$ is connected, we need to show that $T$ is in fact a tree. This follows from the structural properties of the anchor assignment, which ensure that no cycles are introduced during Phase 3. Additionally, we analyze the probe complexity of each BFS used to discover anchor paths, leveraging both the spectral properties of random walks and the expansion characteristics of the graph $G$ .

Local Algorithm Implementation

To locally determine whether an edge $(u,v)$ belongs to $E^{\prime}$ , we first establish a key property of the shortest path between a vertex $u\in V\setminus S$ and its anchor. Specifically, an edge $(u,v)$ is in $E^{\prime}$ if and only if it lies on the path from $u$ to its anchor or on the path from $v$ to its anchor.

This property enables a local algorithm to answer edge-membership queries by simulating the first two phases of the global algorithm – random walk sampling and core tree construction – and then performing BFS from both $u$ and $v$ to identify the corresponding anchor paths.

For consistency, in Phase 1, the local algorithm always uses the same random bits for random walks across all queries, ensuring that the locally reconstructed subgraph is consistent with the global construction.

Edge-Membership Query: Is $(u,v)\in E^{\prime}$ ?

$\blacksquare$

Step 1: Simulate Random Walks. Run the same random walks as performed in the global algorithm.
$\blacksquare$
Step 2: Construct Core Tree. Extract the core tree $T_{0}=(S,E^{\prime})$ from the random walk trajectories.
- –
  
  If $(u,v)\in E^{\prime}$ , return Yes.
$\blacksquare$
Step 3: Identify Anchor Paths. Otherwise, perform BFS from both $u$ and $v$ to find their respective paths to their anchors.
- –
  
  If edge $(u,v)$ lies on either of these two paths, return Yes; otherwise, return No.

1.3.2 Spanning Tree in Random Graphs

To break the $\Omega(\sqrt{n})$ lower bound for graphs drawn from the Erdős-Rényi distribution, we leverage the tools developed previously along with a key property of $G(n,p)$ : each pair of vertices forms an edge independently with probability $p=n^{\delta-1}$ , where $\delta>0$ is constant.

A simple initial observation is as follows. For a pair of non-adjacent vertices $u$ and $v$ in $G\sim G(n,p)$ , independent BFS explorations from $u$ and $v$ are unlikely to intersect until each has visited roughly $\sqrt{n^{1-\delta}}$ vertices. Indeed, for two disjoint sets $V_{1},V_{2}$ of size $o(\sqrt{n^{1-\delta}})$ , the number of potential edges between them is $o(n^{1-\delta})$ , and each edge exists independently with probability $p$ , giving an expected number of edges $o(1)$ between the BFS frontiers.

Beyond the $\sqrt{n}$ Barrier

This observation motivates a new approach that achieves probe complexity $R=\tilde{\Theta}(\sqrt{n^{1-\delta}})$ . We first perform $R$ independent random walks to construct a small core tree $T_{0}$ spanning a vertex set $S$ . Then, for each vertex, we use at most $R$ probes to attempt to find a path to an anchor in $S$ . Vertices that succeed are called good.

Vertices that fail to find their anchors within this limited BFS are called bad. For each bad vertex $u$ , we exploit properties of the Erdős-Rényi distribution to define a recovery set $IP(u)$ of size up to $n^{\delta}$ , corresponding to a long path in the subgraph. A key property, proved in the full version of this paper [46], is that BFS explorations from vertices in $\operatorname{IP}(u)$ rarely intersect, ensuring that the combined BFS from $IP(u)$ covers up to $\sqrt{n^{1-\delta}}\cdot n^{\delta}=\sqrt{n^{1+\delta}}$ distinct vertices. By properties of random walks, this guarantees that $IP(u)$ contains at least one good vertex, connecting every bad vertex to the core tree. Since the algorithm maintains exactly $n-1$ edges, the resulting subgraph is connected and acyclic, i.e., a spanning tree.

However, if the algorithm uses only $\tilde{\Theta}(\sqrt{n^{1-\delta}})$ probes, the guarantee that $IP(u)$ reaches size $n^{\delta}$ holds only when $\delta\leq 1/3$ . Accordingly, the analysis is divided into two cases:

$\blacksquare$

For $\delta\leq 1/3$ , the procedure above achieves probe complexity $\tilde{\Theta}(\sqrt{n^{1-\delta}})$ .
$\blacksquare$

For $\delta>1/3$ , each vertex $u$ is connected to a restricted set $RIP(u)$ , smaller than $IP(u)$ . Using vertex-pair probes in the general graph model (see Section 2) and the fact that each pair forms an edge with probability $p$ , we still achieve probe complexity $\tilde{\Theta}(\sqrt{n^{1-\delta}})$ .

Proof Techniques

To analyze the algorithm rigorously, we introduce functions that characterize the structure of the sets $\{IP(u)\}_{u\in V}$ and $\{RIP(u)\}_{u\in V}$ . This function-based framework for average-case LCA analysis was proposed by Biswas et al. [10]. However, it is highly problem-specific: different algorithms require custom function definitions.

1.3.3 Minimum Spanning Tree

Moving from unweighted spanning trees to minimum spanning trees introduces new challenges, as the structure of the output is no longer determined solely by connectivity, but also by the relative ordering of edge weights. We focus on expander graphs with integer edge weights drawn from $\{1,2,\dots,W\}$ . As discussed in the full version [46], designing an LCA with sublinear probe complexity for the MST problem on expander graphs with arbitrarily assigned edge weights is impossible, even when $W=2$ .

Motivated by this impossibility result, we instead consider an average-case setting in which the weight of each edge is sampled independently and uniformly from $\{1,2,\dots,W\}$ . In this setting, we show that it is indeed possible to design a local computation algorithm with sublinear probe complexity for computing an exact minimum spanning tree, as formalized in Theorem 1.6.

Here we use an observation that goes back to Kruskal’s algorithm and was exploited by Chazelle, Rubinfeld, and Trevisan in their sublinear MST weight estimation work [17]. Consider a connected graph $G$ with edge weights in $\{1,2,\dots,W\}$ for some integer $W\geq 2$ . Let $G_{\leq i}$ denote the subgraph of $G$ consisting of all edges of weight at most $i$ .

The MST of $G$ can be constructed incrementally. First, compute a minimum spanning forest (MSF) $F_{\leq 1}$ of $G_{\leq 1}$ , which consists of an MST for each connected component of $G_{\leq 1}$ . Next, add a suitable set of weight-2 edges $E_{2}$ to obtain

F_{\leq 2}=F_{\leq 1}\cup E_{2},

an MSF of $G_{\leq 2}$ . Continuing inductively, given an MSF $F_{\leq i}$ of $G_{\leq i}$ , we add a set of weight- $(i+1)$ edges $E_{i+1}$ to form

F_{\leq i+1}=F_{\leq i}\cup E_{i+1},

which is an MSF of $G_{\leq i+1}$ and contains the MST of each connected component of $G_{\leq i+1}$ . Since $G$ is connected, the resulting forest $F_{\leq W}$ is a minimum spanning tree of $G$ at the final step.

The key technical difficulty here is to ensure consistency across different weight layers, since the LCA must answer membership queries for edges without explicitly constructing forests $F_{\leq i}$ . Unlike in the unweighted setting, the decision for an edge of weight $i$ depends on the connectivity structure induced by all lower-weight edges, and directly simulating the MSF construction on $G_{\leq i}$ may incur superlinear probe complexity.

To overcome this issue, we rely on two ideas. First, we exploit structural properties induced by the random weight distribution. This weakens dependencies between decisions for edges across different weight layers, and allows us to determine membership using only local information. Second, within each local weight layer, we use a spanning tree of the underlying unweighted graph as a global reference structure. The tree encodes both connectivity and acyclicity of the graph, which we leverage to help determine whether a queried edge should be retained.

Hierarchy by Random Weights

Given a $d$ -regular expander graph, if each edge is sampled independently with probability $p$ , then as long as $p$ avoids a narrow critical interval (e.g., $(\frac{1-\varepsilon}{d},\frac{1+\varepsilon}{d})$ for sufficiently small constant $\varepsilon$ ), the resulting subgraph $G_{p}$ satisfies one of the following: either all connected components are small, of size $O_{\varepsilon}(\log n)$ , or there is a single giant connected component of size $\Omega_{\varepsilon}(n)$ with fast mixing time $O(\log^{2}n)$ , while the remaining components are small, of size $O_{\varepsilon}(\log n)$ .

This phenomenon yields a layered view of the graph, revealing edges in increasing order of weight. Starting from $G_{\leq 1}$ , with high probability the graph contains a unique giant component $L_{\leq 1}$ , while all remaining components are small. As the threshold increases, the giant component gradually grows by absorbing smaller components, and each $G_{\leq i}$ continues to consist of a single giant component $L_{\leq i}$ together with only small components. We illustrate the hierarchy in the following figure, and note that $L_{\leq W}=G$ .

Figure 2: Hierarchy of giant components across weight thresholds.

We discuss this hierarchy formally in the full version of this paper [46]. Intuitively, for small components, we can explore the entire component with a few queries and then use the full information to compute its MST or extract edges to add toward a larger MST. For the giant component $L_{\leq 1}$ , since it only contains weight- $1$ edges, we can apply a random-walk–based approach, as previously described, to determine whether any given edge belongs to its MST.

Now the problem is reduced to, for each $i\in[W-1]$ , select appropriate edges to connect small components between $L_{\leq i}$ and $L_{\leq i+1}$ , i.e., those components of $G_{\leq i}$ that are absorbed into $L_{\leq i+1}$ when edges of weight $i+1$ are added. Note that every such component only contains edges with weight at most $i$ . To this end, we apply the second idea, namely leveraging an unweighted spanning tree on $L_{\leq i+1}$ , which allows us to iteratively construct a minimum spanning forest of $G_{\leq i+1}$ .

Unweighted Spanning Tree for Reference

Let us focus on the small components that lie between $L_{\leq 1}$ and $L_{\leq 2}$ for illustration. For each such small component, say $C$ , our goal is to identify a weight- $2$ edge incident to $C$ , such that the collection of all selected weight- $2$ edges connects these small components to $L_{\leq 1}$ without creating cycles.

To identify such edges, we use an (unweighted) spanning tree of $L_{\leq 2}$ as a reference. For intuition, fix any (unweighted) spanning tree $T$ of $L_{\leq 2}$ and contract each component $C$ into a super-vertex. The resulting graph remains connected. Moreover, every edge between super-vertices must have weight $2$ in $G$ ; otherwise, the corresponding super-vertices would already be merged.

This implies that the edges of $T$ provide useful structural information. For each component $C$ , we select a weight- $2$ edge incident to $C$ that appears in $T$ . To guarantee acyclicity, we define a partial ordering, called rank, over vertices within each small component with respect to $T$ . Importantly, $T$ is locally accessible using Theorem 1.4, provided that we can support adjacency-list probes to $L_{\leq 2}$ using the LCA constructed for expander graphs. Combining these ideas yields a local procedure for identifying such edges.

Combining these procedures yields the final LCA for determining whether a queried edge belongs to the MST.

Due to space constraints, we defer the detailed algorithms and proofs for our average-case LCA and minimum-spanning-tree results to the full version [46].

1.4 Other Related Work

LCA for Sparse Spanning Subgraphs (Spanners)

We review the literature on Local Computation Algorithm (LCA) for two closely related problems: sparse spanning subgraphs and graph spanners. Both aim to consistently provide local access to a sparsified version of a graph while preserving certain structural properties. LCAs for sparse spanning subgraphs primarily focus on ensuring connectivity with as few edges as possible. In contrast, LCAs for spanners aim to preserve approximate pairwise distances, where a $k$ -spanner means that it preserves all pairwise distances within a multiplicative factor $k\geq 1$ . Since most existing works trade off between sparsity and stretch, we discuss both lines of research together.

A series of works [40, 39, 43] study LCAs for sparse spanning subgraph in minor-free graphs. Levi et al. [38] designed an LCA for hyperfinite graphs with probe complexity independent of $n$ , though super-exponential in $d$ and $1/\varepsilon$ . Lenzen and Levi [36] gave an LCA for $d$ -bounded graphs with probe complexity $O(n^{2/3}\cdot\mathrm{poly}(d/\varepsilon))$ and stretch $O\left(\frac{\log n\cdot(d+\log n)}{\varepsilon}\right)$ . Bodwin et al. [11] gave an adjacency oracle for a spanning subgraph with $(1+\varepsilon)n$ edges. This model allows centralized preprocessing and answers each adjacency probe in $\tilde{O}(1)$ time. With total preprocessing time $\tilde{O}(n/\varepsilon)$ , their algorithm implies an $\tilde{O}(n/\varepsilon)$ -time LCA: one can construct an adjacency oracle for each query and erase the memory after that. Levi et al. [37] also extended their LCA to well-clusterable graphs. Suppose $G$ is a graph that can be partitioned into a constant number of vertex sets, each of which induces an expander and has conductance at most $\phi_{\text{out}}$ in $G$ . Their algorithm finds a spanning subgraph with $(1+\varepsilon)n$ edges, achieves probe complexity $O(\sqrt{n}+\phi_{\text{out}}n)$ and stretch $\Theta(\log n)$ .

For spanners with constant stretch, Parter et al. [45] and Arviv et al. [3] proposed LCAs that construct $(2k-1)$ -spanners with $O(n^{1+1/k})$ edges for small $k\in\{2,3\}$ , and more generally, $O(k^{2})$ -spanners with $O(n^{1+1/k})$ edges for arbitrary $k\geq 1$ . In particular, Arviv et al. [3] improved the probe complexity to $O(n^{1-1/k})$ for the $(2k-1)$ -spanners, and to $O(n^{2/3}d^{2})$ for the $O(k^{2})$ -spanners.

LCA for Other Problems

LCAs have also been extensively studied for several classical problems, including maximal independent set (MIS) [28, 42, 30, 29], maximal matching [31, 50, 44, 42, 8], and vertex coloring [22, 23, 19, 16]. Recent works have also established lower bounds for LCAs [7, 5]. Despite the above, there are also interesting applications that leverage LCAs. For example, [33, 32, 34, 35] employ LCAs to promote the development of learning theory, while [4] applies LCAs to analyze an algorithm in the context of the Stochastic Matching problem.

Average-Case LCA

Previously, local algorithms were studied by [14, 13, 26] in the preferential attachment model, a well-known random graph model characterizing real-world networks. The algorithm they studied is called “local information algorithms”, a restricted version of LCA. More recently, Biswas et al. [10] initiated and formalized the study of average-case LCAs, focusing on the construction of $k$ -spanners (and sparse spanning subgraphs) when the input graph is drawn from various random graph models, including Preferential Attachment and Erdős-Rényi graphs with certain parameters. The probe complexity of their algorithms depends on the characteristics of the specific model. In particular, for the Preferential Attachment model, they design an LCA that provides local access to an $O(\log n)$ -stretch spanning tree using $O(\mu\sqrt{n})$ probes in the worst case and $O(\mu\log^{3}n)$ probes in expectation over random queries, where $\mu$ denotes the expected degree. For Erdős–Rényi graphs $G\sim\mathcal{G}(n,p)$ , when $np=n^{\delta}$ , a $(2/\delta+5)$ -stretch spanner with $n+o(n)$ edges can be accessed using $O\left(\min(n^{\delta},n^{1-\delta}\log n)\right)$ probes; for $p\geq 7\log n/n$ , another algorithm constructs a sparse spanning subgraph with $n+o(n)$ edges using $\tilde{O}(\Delta)$ probes, where $\Delta=np$ is the expected degree.

Phase Transition of Random Subgraphs

Percolation theory, initiated by Broadbent and Hammersley [15] in 1957, studies probabilistic models of random subgraphs: Given a base graph $G$ , the percolated subgraph $G_{p}$ is obtained by retaining each edge of $G$ independently with probability $p$ . In this line of work, one central topic is to understand the phase transition behavior of $G_{p}$ as the percolation probability $p$ increases. Typically, there exists a critical threshold separating a subcritical regime, in which all connected components have size $O(\log n)$ with high probability, from a supercritical regime, in which a unique giant connected component of size $\Omega(n)$ emerges. For the Erdős–Rényi model $G(n,p)$ , this threshold is $p=1/n$ [21]. Similar phenomena have been established for other base graphs, such as the hypercube [1, 12], general graphs under degree and spectral assumptions [18], and in particular for $d$ -regular expanders, [25, 20] characterized the emergence and expansion of the giant component.

MSTs on Graphs with Randomly Assigned Edge Weights

The study of MSTs on graphs with randomly assigned edge weights is a classical topic in theoretical computer science. Many previous works have approached this problem from various perspectives, particularly focusing on estimating the weight of the MST when the edge lengths are drawn independently from identical distributions [27, 9, 49, 24, 6].

2 Preliminaries

In this paper, we use $[k]$ to denote the set $\{1,2,\cdots,k\}$ for positive integer $k$ . For input graph $G=(V,E)$ , throughout this paper we assume $V=[n]$ . For $u\in V$ , we use $\Gamma_{G}(u)$ to denote the neighborhood of $u$ in $G$ , i.e. $\Gamma_{G}(u):=\{v\in V|(u,v)\in E\}$ . We omit the subscript when it is clear from context.

We will use the following definitions of paths, path orderings, and lexicographically-least shortest path.

Definition 2.1.

For a set of vertices $S$ , $\text{Smallest}(S)$ (resp. $\text{Largest}(S)$ ) denotes the vertex with smallest (resp. largest) ID in set $S$ .

Definition 2.2 (path).

For graph $G=(V=[n],E)$ , we call a sequence of vertices $P=(u_{1},u_{2},\cdots,u_{k})$ a path starting at $u_{1}$ and ending at $u_{k}$ , if $u_{i}\in V$ for $i\in[k]$ and $(u_{i},u_{i+1})\in E$ for $i\in[k-1]$ . We use following notations: (1) $V(P)$ : vertex set induced by $P$ , i.e. $\{u_{1},u_{2},\cdots,u_{k}\}$ ; (2) $E(P)$ : edge set induced by $P$ , i.e. $\{(u_{1},u_{2}),(u_{2},u_{3})\cdots,(u_{k-1},u_{k})\}$ ; (3) $\ell(P)$ : length of $P$ , i.e. $|E(P)|$ ; (4) $P^{(i)}$ : the $i$ -th vertex in $P$ , i.e. $u_{i}$ .

Definition 2.3 (path ordering).

For two paths $P_{1}$ and $P_{2}$ starting from same vertex, we say $P_{1}\prec P_{2}$ if $\ell(P_{1})<\ell(P_{2})$ ; or $\ell(P_{1})=\ell(P_{2})$ , and from starting vertex to ending vertex, $P_{1}$ has smaller lexicographical order than $P_{2}$ .

Definition 2.4 (lexicographically-least shortest path).

A path $(u,w_{1},w_{2},\cdots,v)$ from $u$ to $v$ is the lexicographically-least shortest path if for any other path $(u,w^{\prime}_{1},w^{\prime}_{2},\cdots,v)$ from $u$ to $v$ , it holds that

(u,w_{1},w_{2},\cdots,v)\prec(u,w^{\prime}_{1},w^{\prime}_{2},\cdots,v).

We use $P_{G}(u,v)$ to denote the lexicographically-least shortest path from $u$ to $v$ in graph $G$ . Specifically, note that for any vertex $u\in V$ , $V(P_{G}(u,u))=\{u\}$ and $E(P_{G}(u,u))=\emptyset$ .

We formally define the Erdős-Rényi graph.

Definition 2.5 (Erdős-Rényi graphs).

For a function $p=p(n)$ , a graph $G\leftarrow{}G(n,p)$ is an Erdős-Rényi random graph if for every pair $(u,v)\in[n]\times[n]$ with $u\neq v$ , edge $(u,v)$ is added to $E(G)$ with probability $p$ independently.

2.1 Access Models

We will consider the following access models.

Adjacency List Model.

In the adjacency list model, a local computation algorithm (LCA) accesses the graph $G=([n],E)$ using two types of probes. The probe Deg $(v)$ returns the degree of a vertex $v$ . The probe Nbr $(v,i)$ returns the $i^{\text{th}}$ neighbor of vertex $v$ according to its adjacency list if $i\leq\texttt{Deg}(v)$ , and returns $\bot$ otherwise. For weighted graphs, Nbr $(v,i)$ also returns the weight of corresponding edge.

General Graph Model.

In the general graph model, the LCA has access to the same Deg $(v)$ and Nbr $(v,i)$ probes as in the adjacency list model, and is additionally allowed to perform vertex-pair probes. Specifically, a vertex-pair probe Exists $(u,v)$ returns true if the edge $(u,v)\in E$ , and false otherwise. This model provides more flexibility by enabling direct probes about whether a specific edge is present in the graph.

2.2 Searching for the Lexicographically-Least Shortest Path

Throughout this paper, we frequently need to find, for a given vertex $u$ and a given set of vertices $S$ , the lexicographically-least shortest path from $u$ to $S$ . Recall from Definition 2.3 that this is the path $P_{G}(u,\mathrm{anc}_{S}(u))$ minimizing the tuple

\bigl(\ell(P),\;P^{(1)},P^{(2)},\dots,P^{(\ell(P))}\bigr),

(1)

in lexicographic order, where $\ell(P)$ denotes the length of $P$ and $P^{(j)}$ denotes the $j$ -th vertex on $P$ (starting from $u$ ).

To compute this path locally and efficiently, we perform a modified Breadth-First Search (BFS) from $u$ . As in a standard BFS, vertices are explored layer by layer according to their distance from $u$ . However, within the same layer, vertices are processed according to the lexicographic order of the shortest paths by which they were first discovered.

More precisely, when a vertex $v$ is first discovered, the algorithm stores the corresponding shortest path from $u$ to $v$ . Among all vertices at the same BFS level, the next vertex to process is the one whose stored path is lexicographically least according to (1). As soon as the search discovers that a vertex $w$ has a neighbor in $S$ , the algorithm terminates and outputs the corresponding path from $u$ to $w$ , extended by the edge $(w,s)$ , where $s$ is the smallest-ID neighbor of $w$ in $S$ .

By induction on the BFS layers, one can verify that every vertex is first discovered through the lexicographically-least shortest path from $u$ to that vertex. This guarantees that the resulting path is lexicographically least among all shortest paths from $u$ to $S$ .

2.3 Conductance, Expander graphs and Random walks

For a graph $G=(V,E)$ with degree at most $d$ , we modify graph $G$ to get a $d$ -regular graph $G_{reg}$ by adding half-weighted self-loops to each vertex in $G$ so that each vertex has degree $d$ . In this paper, instead of directly performing random walk on $G$ , we perform lazy random walk on $G_{reg}$ . A lazy random walk is a random walk that stays at the current vertex w.p. $\frac{1}{2}$ at each step. Note that this is equivalent to a random walk on $G$ which stays at the current vertex $v$ w.p. $\frac{2d-deg(v)}{2d}$ and moving to each neighbor w.p. $\frac{1}{2d}$ . Each step of such a random walk can be implemented by uniformly sampling an integer $i$ from $[2d]$ and making a probe Nbr $(v,i)$ .

Using the notion of graph conductance, we have the following corollary for lazy random walks on $G_{\text{reg}}$ ; although it is a direct consequence of the classical mixing-time bounds of Sinclair and Jerrum [48], we use the formulation of [37] which is tailored to our setting.

Definition 2.6 (conductance).

Let $G=(V,E)$ be a graph and $S\subseteq V$ be a vertex set. Denote $\mu_{G}(S):=\sum_{v\in S}deg(v)$ and $\phi_{G}(S):=\frac{|E(S,V\setminus S)|}{\mu_{G}(S)}$ , where $E(A,B)$ denotes the set of edges with one vertex in $A$ and the other in $B$ .

The conductance of $G$ is defined by $\phi_{G}:=\min\limits_{\begin{subarray}{c}\emptyset\subsetneq S\subseteq V\\ \mu_{G}(S)\leq\mu_{G}(V)/2\end{subarray}}\phi_{G}(S)$ .

We call a graph $G$ an expander if $\phi_{G}\geq\phi$ for some universal constant $\phi>0$ .

Corollary 2.7 ([37]).

Let $G=(V,E)$ be a connected $d$ -bounded degree graph on $n$ vertices and let $v\in V$ . If we perform a lazy random walk in $G_{reg}$ starting from $v$ , of length at least $\tau(G_{reg}):=\frac{c\log(n)}{\phi^{2}(G)}$ for some large constant $c$ , then the probability that this walk ends at $u$ is at least $\left(\frac{1}{2n}\right)$ for every $u\in V$ .

3 LCA for Spanning Tree on Expanders

In the following, we first present a global algorithm for constructing a spanning tree in expander graphs. Then we show how to locally implement it to obtain the LCA and prove Theorem 1.4.

3.1 A Global Algorithm for Constructing Spanning Trees

The global algorithm (which runs in polynomial time) works in three phases. In Phase 1, it starts by sampling a vertex $s$ as a seed and then performs $O(\sqrt{n})$ independent length- $\tau$ lazy random walks from $s$ on graph $G_{\mathrm{reg}}$ , where $\tau\geq\tau(G_{\mathrm{reg}})$ is as defined in Corollary 2.7, which is large enough for the random walk to mix.

We denote by $S$ all the vertices met, and by $H$ the set of edges (discarding self-loops) seen during random walks. Note that for every vertex $v\in S$ , there is a path from $s$ to $v$ with length at most $\tau$ , only using edges in $H$ . Let $G_{0}:=(S,H)$ be the graph with vertex set $S$ and edge set $H$ .

Then in Phase 2, the algorithm finds the spanning tree, denoted as $T_{0}=(S,H^{\prime})$ of $G_{0}$ . This can be done by performing BFS from $s$ in $G_{0}$ . Note that the tree can be viewed as a tree rooted at $s$ of depth $O(\tau)$ . In the following, we will call the tree $T_{0}=(S,H^{\prime})$ a core tree.

We have the following definition that will be used in Phase 3.

Definition 3.1 (anchor).

Let $G=(V,E)$ and $S$ be a subset of $V$ . A vertex $v\in S$ is said to be the anchor of $u\in V\setminus S$ if for every vertex $w\in S\setminus\{v\}$ , $P_{G}(u,v)\prec P_{G}(u,w)$ . Informally speaking, $P_{G}(u,v)$ is the lexicographically-least shortest path among all paths from $u$ to $S$ , and $v$ is the vertex in $S$ that is reached by $P_{G}(u,v)$ .

For $u\in V\setminus S$ , we use $\mathrm{anc}_{S}(u)$ to denote the anchor of $u$ in the set $S$ . For convenience, let $\mathrm{anc}_{S}(u):=u$ if $u\in S$ .

In Phase 3, we extend $T_{0}$ to span all remaining vertices $u$ by connecting them through their anchors $\mathrm{anc}_{S}(u)$ , while maintaining the tree structure locally. Specifically, we employ a subroutine, Algorithm 2, which performs a BFS from a vertex $u\in V\setminus S$ in $G$ , exploring vertices in lexicographical order until a vertex in $S$ is reached.

We formally describe the above procedure in Algorithm 1.

Algorithm 1 Globally Computing a Spanning Tree.

Algorithm 2 FindPath

(G,S,\theta,u)

: explore at most

\theta

vertices to compute path

P_{G}(u,\mathrm{anc}_{S}(u))

for any vertex

u

.

3.1.1 Correctness of Algorithm 1

In this section, we prove that the output subgraph $T$ is indeed a spanning tree of the input graph $G$ .

Theorem 3.2.

If every invocation of FindPath does not return $\bot$ in Algorithm 1, then the output graph $T=(V,E^{\prime})$ is a spanning tree of $G$ .

Note that until the beginning of Phase 3, $E^{\prime}$ contains no cycle. We thus put our attention on Phase 3. In Phase 3, each of $\Theta(n)$ vertices outside the $S$ is processed by an iteration, to find a path to the core tree and add it to $E^{\prime}$ . Consider that each of these $\Theta(n)$ iterations in Phase 3 adds a path (probably of length $\log n$ ) to $E^{\prime}$ , it seems that there are far more than $n-1$ edges included in $E^{\prime}$ after Phase 3. However, the following claim indicates that most edges added to $E^{\prime}$ during Phase 3 are added multiple times; hence, $T$ only contains $n-1$ edges.

Lemma 3.3.

For any set $S\subset V$ and $u\in V\setminus S$ , let $v=\mathrm{anc}_{S}(u)$ be the anchor of $u$ w.r.t. $S$ and path $P_{G}(u,v)=(u,u_{1},\cdots,u_{k},v)$ be the lexicographically-least shortest path. Then for $i=1,2,\cdots k$ , we have:

	$\displaystyle\mathrm{anc}_{S}(u_{i})=v,$
	$\displaystyle P_{G}(u_{i},v)=(u_{i},u_{i+1},\cdots,u_{k},v).$

Proof.

First, we note that $u_{i}\in V\setminus S$ . Otherwise, $(u,u_{1},\cdots,u_{i})$ becomes a path between $u$ and $S$ strictly shorter than $P_{G}(u,v)$ , which contradicts to Definition 3.1. Let $Q_{i}:=(u_{i},\ldots,u_{k},v)$ .

We prove by contradiction. For the first statement, assume that $\mathrm{anc}_{S}(u_{i})\neq v$ , then there must be a vertex $w\in S\setminus\{v\}$ s.t. $P_{G}(u_{i},w)\prec Q_{i}$ . By Definition 2.3, either $\ell(P_{G}(u_{i},w))<\ell(Q_{i})$ or $\ell(P_{G}(u_{i},w))=\ell(Q_{i})$ and $P_{G}(u_{i},w)$ has smaller lexicographical order than $Q_{i}$ . In both cases, substituting $(u_{i},u_{i+1},\cdots,u_{k},v)$ by $P_{G}(u_{i},w)$ in $P_{G}(u,v)$ yields a path from $u$ to $S$ preceding $P_{G}(u,v)$ . Thus $\mathrm{anc}_{S}(u)\neq v$ by Definition 3.1, leading to a contradiction. Hence $\mathrm{anc}_{S}(u_{i})=v$ for each $i\in[k]$ .

For the second statement, we assume that $P_{G}(u_{i},v)\neq Q_{i}$ . Then similarly there comes a contradiction to $P_{G}(u,v)=(u,u_{1},\cdots,u_{k},v)$ , because substituting $(u_{i},u_{i+1},\cdots,u_{k},v)$ by $P_{G}(u_{i},v)$ in the path $P_{G}(u,v)$ , will result in a path preceding $P_{G}(u,v)$ . This finishes the proof. $\hfill\blacktriangleleft$

Now we formally prove Theorem 3.2.

Proof of Theorem 3.2.

Denote by $T_{0}=(S,H^{\prime})$ the core tree. Let

E_{1}:=H^{\prime}\ \cup\ \bigcup_{u\in V\setminus S}E\bigl(P_{G}(u,\mathrm{anc% }_{S}(u))\bigr)

be the edge set returned by Algorithm 1, and let $T_{1}=(V,E_{1})$ . Since every invocation of FindPath succeeds, it is easy to see that $T_{1}$ is connected.

It remains to show that $T_{1}$ has exactly $n-1$ edges. We prove by constructing an orientation of all edges in $T_{1}$ . Moreover, we show that under this orientation, the out-degree of every vertex (except for the root $s$ ) is exactly $1$ . This implies that $T_{1}$ has exactly $n-1$ edges.

First, we orient every edge of the core tree $T_{0}$ toward the root $s$ in a natural way. Thus each vertex in $S\setminus\{s\}$ has exactly one outgoing core-tree edge.

Next orient every edge on each path $P_{G}(u,\mathrm{anc}_{S}(u))$ , $u\in V\setminus S$ , toward the anchor $\mathrm{anc}_{S}(u)$ . This orientation is well-defined on the union of all these paths. Indeed, suppose a vertex $x\in V\setminus S$ lies on some path $P_{G}(u,\mathrm{anc}_{S}(u))$ . By Lemma 3.3, the suffix of that path starting from $x$ is exactly $P_{G}(x,\operatorname{anc}_{S}(x))$ . Therefore, every path that passes through $x$ shares the same next edge out of $x$ toward $S$ .

Consequently, every vertex $x\in V\setminus S$ has exactly one outgoing edge in this orientation, namely the first edge of $P_{G}(x,\operatorname{anc}_{S}(x))$ . Moreover, no path $P_{G}(u,anc_{S}(u))$ has an internal vertex in $S$ ; otherwise, a proper prefix would already reach $S$ , contradicting the definition of the anchor path. Thus Phase 3 creates no outgoing edge from any vertex of $S$ .

Thus, in the oriented graph,

\sum_{x\in V}\operatorname{outdeg}(x)=|V\setminus S|+|S\setminus\{s\}|=n-1.

Since each edge contributes exactly one to the sum of out-degrees, we have $|E_{1}|=n-1$ . Having shown that $T_{1}$ is connected, it is a spanning tree of $G$ . $\hfill\blacktriangleleft$

3.2 Local Implementation

We show how to implement the global Algorithm 1 locally, i.e., for the concerned edge $(u,v)$ , we need some local procedure to determine whether $(u,v)$ belongs to the final output $E^{\prime}$ . From a high-level view, it is easy to see that Phase 1 and Phase 2 can be implemented in $\tilde{O}(\sqrt{n})$ probes. Note that we always use same random bits to perform random walks in Phase 1, thus it remains consistent over any sequence of queries.

However, to implement Phase 3, we should check if $(u,v)$ appears in any path added to $E^{\prime}$ during iterations, but directly performing these checks requires $\Omega(n)$ probes. Thanks to the following lemma for locality, we can implement it with fewer probes.

Claim 3.4.

With respect to $S$ and output $T$ in Algorithm 1, for any edge $(u,v)$ with $\{u,v\}\nsubseteq S$ , we have $(u,v)\in E(T)$ if and only if $(u,v)\in P_{G}(u,\mathrm{anc}_{S}(u))$ or $(u,v)\in P_{G}(v,\mathrm{anc}_{S}(v))$ .

Proof.

If $(u,v)\in P_{G}(u,\mathrm{anc}_{S}(u))$ or $(u,v)\in P_{G}(v,\mathrm{anc}_{S}(v))$ , then obviously we have $(u,v)\in E(T)$ . In the following, we consider the other direction.

If $(u,v)\in E(T)$ , then there exists some vertex $w\in V\setminus S$ s.t. $(u,v)\in P_{G}(w,\mathrm{anc}_{S}(w))$ . As $(u,v)\notin S\times S$ , edge $(u,v)$ could only be added to $E^{\prime}$ in Phase 3, hence it must belong to path $P_{G}(w,\mathrm{anc}_{S}(w))$ for some vertex $w$ . Thus, we have either

P_{G}(w,\mathrm{anc}_{S}(w))=(w,\cdots,u,v,\cdots,\mathrm{anc}_{S}(w)),

or

P_{G}(w,\mathrm{anc}_{S}(w))=(w,\cdots,v,u,\cdots,\mathrm{anc}_{S}(w)).

For both cases, we apply Lemma 3.3 on $P_{G}(w,\mathrm{anc}_{S}(w))$ w.r.t. the vertex of $(u,v)$ that appears earlier in the path. Thus we have either $(u,v)\in P_{G}(u,\mathrm{anc}_{S}(u))$ or $(u,v)\in P_{G}(v,\mathrm{anc}_{S}(v))$ . $\hfill\vartriangleleft$

Algorithm 3 inTree

(G,(u,v))

: locally answer whether

(u,v)

belongs to spanning tree induced by Algorithm 1.

Now we have Local Computation Algorithm 3 to simulate Algorithm 1, which outputs membership of any concerned edge $(u,v)$ . Recall that the random bits are predetermined and thus Algorithm 3 always outputs a consistent answer on every query.

Lemma 3.5.

For the same input graph and public random bits, Algorithm 3 returns Yes on query of edge $(u,v)$ if and only if $(u,v)\in E(T)$ in Algorithm 1.

Proof.

In Algorithm 3, random bits are only used to select a seed vertex and perform random walks in Phase 1, and there is no randomness in Phase 2 and Phase 3. Using the same random bits, in both algorithms, the core tree $T_{0}=(S,H^{\prime})$ is the same, and thus they agree on edge $(u,v)\in S\times S$ . Additionally, by ˜3.4, the two algorithms also agree on edge $(u,v)\notin S\times S$ . Hence Algorithm 3 faithfully simulates the spanning-tree membership of every edge computed by Algorithm 1. $\hfill\blacktriangleleft$

3.3 Probe Complexity of the LCA

To bound the probe complexity of Algorithm 3, we first bound the probe complexity of FindPath (Algorithm 2).

Lemma 3.6.

Let $G=(V,E)$ be $d$ -bounded graph with conductance $\phi_{G}\geq\phi$ . Let $\tau\geq\tau(G_{reg})$ and $r>0$ be integers. With respect to $r$ independent length- $\tau$ lazy random walks on $G_{reg}$ , let $S$ be the set of vertices in the trajectory of these random walks. Then for any given set of vertices $Q$ s.t. $|Q|\cdot r\geq 100n\log n$ , we have $|Q\cap S|\geq 1$ with probability at least $1-\frac{1}{n^{10}}$ . ⁵⁵5To save random bits used by LCA, it is sufficient to let these random walks be $\log n$ -wise independent.

Proof.

Let $S_{C}=(v_{\tau}^{(1)},v_{\tau}^{(2)},\cdots,v_{\tau}^{(r)})\subseteq S$ be the set of end-vertex of each random walk. According to Corollary 2.7, we have $\Pr[v_{\tau}^{(i)}=u]\geq\frac{1}{2n}$ for every $i\in[r]$ and $u\in V$ . Let random variable $X_{i}$ indicate the event that the $i$ -th random walk ended at $Q$ and $X:=\Sigma_{i\in[r]}X_{i}$ . Note that $X\geq 1\implies|Q\cap S|\geq 1$ . Then we have

\displaystyle\mathbb{E}[X_{i}]=\Pr[v_{\tau}^{(i)}\in Q]=\Sigma_{u\in Q}\Pr[v_{% \tau}^{(i)}=u]\geq\frac{|Q|}{2n},

and by the linearity of expectation

\displaystyle\mathbb{E}[X]=\mathbb{E}[\Sigma_{i\in[r]}X_{i}]=\Sigma_{i\in[r]}% \mathbb{E}[X_{i}]\geq\frac{r\cdot|Q|}{2n}\geq 50\log n.

Then a standard argument using Chernoff-Hoeffding bound finishes the proof. $\hfill\blacktriangleleft$

Claim 3.7.

Let $G=(V,E)$ be $d$ -bounded graph with conductance $\phi_{G}\geq\phi$ . With respect to set $S$ in Algorithm 3, then FindPath $(G,S,\sqrt{n},u)$ makes $O(d\sqrt{n})$ probes for any given vertex $u$ and does not return $\bot$ with probability at least $1-\frac{1}{n^{2}}$ .

Proof.

Let $Q$ be the set of the first $\sqrt{n}$ distinct vertices explored from $u$ , by the BFS procedure defined in Section 2.2. Note that $r:=\Theta(\sqrt{n}\cdot\log n)$ and $|Q|=\sqrt{n}$ , thus $|Q|\cdot r\geq 100n\log n$ by choosing proper constant. In this scenario, Lemma 3.6 tells that, with probability at least $1-\frac{1}{n^{10}}$ , the BFS in FindPath $(G,S,\sqrt{n},u)$ already finds a vertex in $v\in S$ at the moment that $Q$ is fully explored. Hence it does not return $\bot$ with probability at least $1-\frac{1}{n^{10}}$ .

Let $H:=G[Q]$ denote the subgraph induced by $Q$ , then the probe complexity of BFS is $O(|V(H)|+|E(H)|)$ . As the input graph is $d$ -bounded, the subgraph induced by $Q$ contains at most $d\cdot\left|Q\right|=d\sqrt{n}$ edges. Consider that computing the output path does not need more probes except for revealing all neighbors of $v$ , hence for any given vertex $u\in V\setminus S$ , FindPath $(G,S,\sqrt{n},u)$ finishes in $d\sqrt{n}+d=O(d\sqrt{n})$ probes. $\hfill\vartriangleleft$

Lemma 3.8.

Let $G=(V,E)$ be $d$ -bounded graph with conductance $\phi_{G}\geq\phi$ . Then Algorithm 3 has probe complexity $O(\sqrt{n}(\frac{\log^{2}n}{\phi^{2}}+d))$ .

Proof.

For any edge $e=(u,v)\in E$ , the LCA first performs lazy random walks using at most $r\cdot\tau=O(\frac{\sqrt{n}\log^{2}n}{\phi^{2}})$ probes. Then, refining the random walk trajectory for the BFS tree $T_{0}$ requires no additional probes.

According to ˜3.7, a single call of FindPath $(G,S,\sqrt{n},w)$ makes $O(d\sqrt{n})$ probes for any given vertex $w$ . Thus FindPath $(G,S,\sqrt{n},u)$ and FindPath $(G,S,\sqrt{n},v)$ together make $O(d\sqrt{n})$ probes.

Overall, Algorithm 3 makes $O(\frac{\sqrt{n}\log^{2}n}{\phi^{2}})+O(d\sqrt{n})=O(\sqrt{n}(\frac{\log^{2}n}% {\phi^{2}}+d))$ graph probes on any given edge. This finishes the proof. $\hfill\blacktriangleleft$

3.4 Proof of Theorem 1.4

We recall Theorem 1.4 for convenience. See 1.4

Proof.

According to ˜3.7, invocation of FindPath $(G,S,\sqrt{n},u)$ makes $O(d\sqrt{n})$ probes for any given vertex $u$ , and it does not return $\bot$ with probability at least $1-\frac{1}{n^{2}}$ . By a union bound over all vertices, with probability at least $1-\frac{1}{n}$ , every invocation of FindPath does not return $\bot$ in Algorithm 1. Hence, by Theorem 3.2 and Lemma 3.5, the subgraph $T$ is a spanning tree of $G$ . By using consistent random bits, Algorithm 3 satisfies Definition 1.1 and is thus an LCA for spanning tree.

It remains to bound the depth of $T$ . By Corollary 2.7, the diameter of $G$ is at most $\tau(G_{\mathrm{reg}})=O(\log n/\phi^{2})$ . For every vertex $x\in S$ , the core tree $T_{0}$ contains a path from the seed $s$ to $x$ of length $O(\tau)$ , because each vertex of $S$ is visited by a length- $\tau$ random walk starting from $s$ , and $T_{0}$ is a BFS tree of the graph induced by the recorded walk edges.

Now consider any vertex $u\in V\setminus S$ . In $T$ , the vertex $u$ is connected to its anchor $a(u)=\operatorname{anc}_{S}(u)$ by the path $P_{G}(u,a(u))$ . This path is shortest, and therefore has length at most $\operatorname{diam}(G)\leq\tau$ . Since $a(u)\in S$ is connected to $s$ in $T_{0}$ by a path of length $O(\tau)$ , the distance from $s$ to $u$ in $T$ is $O(\tau)=O(\log n/\phi^{2})$ . Thus $T$ has depth $O(\log n/\phi^{2})$ . $\hfill\blacktriangleleft$

References

[1] Miklós Ajtai, János Komlós, and Endre Szemerédi. Largest random component of ak-cube. Combinatorica, 2(1):1–7, 1982. doi:10.1007/BF02579276.
[2] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1132–1139. SIAM, 2012. doi:10.1137/1.9781611973099.89.
[3] Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne. Improved Local Computation Algorithms for Constructing Spanners. In Nicole Megow and Adam Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:23, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.42.
[4] Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld. Stochastic matching via in-n-out local computation algorithms. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1055–1066, 2025. doi:10.1145/3717823.3718279.
[5] Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Madhu Sudan. Lower bounds for non-adaptive local computation algorithms. arXiv preprint, 2025. doi:10.48550/arXiv.2505.00915.
[6] Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, and Jamie Tucker-Foltz. Models of random spanning trees. arXiv preprint, 2024. doi:10.48550/arXiv.2407.20226.
[7] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Local computation algorithms for maximum matching: New lower bounds. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2322–2335. IEEE, 2023. doi:10.1109/FOCS57990.2023.00143.
[8] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Sublinear time algorithms and complexity of approximate maximum matching. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 267–280. ACM, 2023. doi:10.1145/3564246.3585231.
[9] Andrew Beveridge, Alan Frieze, and Colin McDiarmid. Random minimum length spanning trees in regular graphs. Combinatorica, 18(3):311–333, 1998. doi:10.1007/PL00009825.
[10] Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. Beyond worst case local computation algorithms. arXiv preprint, 2025. arXiv:2403.00129.
[11] Greg Bodwin and Henry Fleischmann. Spanning adjacency oracles in sublinear time, 2024.
[12] Béla Bollobás, Yoshiharu Kohayakawa, and Tomasz Łuczak. The evolution of random subgraphs of the cube. Random Structures & Algorithms, 3(1):55–90, 1992. doi:10.1002/RSA.3240030106.
[13] Christian Borgs, Michael Brautbar, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier. The power of local information in social networks. In International Workshop on Internet and Network Economics, pages 406–419. Springer, 2012. doi:10.1007/978-3-642-35311-6_30.
[14] Michael Brautbar and Michael J Kearns. Local algorithms for finding interesting individuals in large networks, 2010.
[15] SR Broadbent and JM Hammersley. Percolation processes. i. crystals and mazes. Cambridge Philos. Soc. Math. Proc., 53:629–641, 1957.
[16] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of ( $\delta$ + 1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 471–480, 2019. doi:10.1145/3293611.3331607.
[17] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on computing, 34(6):1370–1379, 2005. doi:10.1137/S0097539702403244.
[18] Fan Chung, Paul Horn, and Linyuan Lu. Percolation in general graphs. Internet Mathematics, 6(3):331–347, 2009. doi:10.1080/15427951.2009.10390644.
[19] Artur Czumaj, Yishay Mansour, and Shai Vardi. Sublinear graph augmentation for fast query implementation. In International Workshop on Approximation and Online Algorithms, pages 181–203. Springer, 2018. doi:10.1007/978-3-030-04693-4_12.
[20] Sahar Diskin and Michael Krivelevich. Expansion in supercritical random subgraphs of expanders and its consequences. Random Structures & Algorithms, 65(3):576–600, 2024. doi:10.1002/RSA.21225.
[21] Paul Erd6s and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17–61, 1960.
[22] Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In European Symposium on Algorithms, pages 394–405. Springer, 2014. doi:10.1007/978-3-662-44777-2_33.
[23] Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.50.
[24] Alan Frieze and Tony Johansson. On edge-disjoint spanning trees in a randomly weighted complete graph. Combinatorics, Probability and Computing, 27(2):228–244, 2018. doi:10.1017/S0963548317000426.
[25] Alan Frieze, Michael Krivelevich, and Ryan Martin. The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Structures & Algorithms, 24(1):42–50, 2004. doi:10.1002/RSA.10100.
[26] Alan Frieze and Wesley Pegden. Looking for vertex number one. The Annals of Applied Probability, pages 582–630, 2017.
[27] Alan M Frieze. On the value of a random minimum spanning tree problem. Discrete Applied Mathematics, 10(1):47–56, 1985. doi:10.1016/0166-218X(85)90058-7.
[28] Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 270–277. SIAM, 2016. doi:10.1137/1.9781611974331.CH20.
[29] Mohsen Ghaffari. Local computation of maximal independent set. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 438–449. IEEE, 2022. doi:10.1109/FOCS54457.2022.00049.
[30] Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1636–1653. SIAM, 2019. doi:10.1137/1.9781611975482.99.
[31] Avinatan Hassidim, Jonathan A Kelner, Huy N Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 22–31. IEEE, 2009. doi:10.1109/FOCS.2009.77.
[32] Jane Lange, Ephraim Linder, Sofya Raskhodnikova, and Arsen Vasilyan. Local lipschitz filters for bounded-range functions with applications to arbitrary real-valued functions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2881–2907. SIAM, 2025. doi:10.1137/1.9781611978322.93.
[33] Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan. Properly learning monotone functions via local correction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 75–86. IEEE, 2022. doi:10.1109/FOCS54457.2022.00015.
[34] Jane Lange and Arsen Vasilyan. Agnostic proper learning of monotone functions: beyond the black-box correction barrier. SIAM Journal on Computing, pages FOCS23–1, 2025.
[35] Jane Lange and Arsen Vasilyan. Robust learning of halfspaces under log-concave marginals. arXiv preprint, 2025. doi:10.48550/arXiv.2505.13708.
[36] Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 87:1–87:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.87.
[37] Reut Levi, Moti Medina, and Omer Tubul. Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), volume 317 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1–60:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.60.
[38] Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, and Asaf Shapira. Constructing near spanning trees with few local inspections. Random Structures & Algorithms, 50(2):183–200, 2017. doi:10.1002/RSA.20652.
[39] Reut Levi and Dana Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms (TALG), 11(3):1–13, 2015. doi:10.1145/2629508.
[40] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, page 826, 2014.
[41] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. Algorithmica, 82(4):747–786, 2020. doi:10.1007/S00453-019-00612-6.
[42] Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica, 77(4):971–994, 2017. doi:10.1007/s00453-016-0126-y.
[43] Reut Levi and Nadav Shoshan. Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.61.
[44] Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 260–273. Springer, 2013. doi:10.1007/978-3-642-40328-6_19.
[45] Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local computation algorithms for spanners. Innovations in Theoretical Computer Science (ITCS), 2019.
[46] Pan Peng and Yuyang Wang. Local computation algorithms for (minimum) spanning trees on expander graphs, 2026. doi:10.48550/arXiv.2602.07394.
[47] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 223–238. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/36.html.
[48] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and computation, 82(1):93–133, 1989. doi:10.1016/0890-5401(89)90067-9.
[49] J Michael Steele. Minimal spanning trees for graphs with random edge lengths. In Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, pages 223–245. Springer, 2002.
[50] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An improved constant-time approximation algorithm for maximum matchings. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 225–234, 2009. doi:10.1145/1536414.1536447.

[bib.bib1] [1] Miklós Ajtai, János Komlós, and Endre Szemerédi. Largest random component of ak-cube. Combinatorica, 2(1):1–7, 1982. doi:10.1007/BF02579276.

[bib.bib2] [2] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1132–1139. SIAM, 2012. doi:10.1137/1.9781611973099.89.

[bib.bib3] [3] Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne. Improved Local Computation Algorithms for Constructing Spanners. In Nicole Megow and Adam Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:23, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.42.

[bib.bib4] [4] Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld. Stochastic matching via in-n-out local computation algorithms. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1055–1066, 2025. doi:10.1145/3717823.3718279.

[bib.bib5] [5] Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Madhu Sudan. Lower bounds for non-adaptive local computation algorithms. arXiv preprint, 2025. doi:10.48550/arXiv.2505.00915.

[bib.bib6] [6] Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, and Jamie Tucker-Foltz. Models of random spanning trees. arXiv preprint, 2024. doi:10.48550/arXiv.2407.20226.

[bib.bib7] [7] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Local computation algorithms for maximum matching: New lower bounds. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2322–2335. IEEE, 2023. doi:10.1109/FOCS57990.2023.00143.

[bib.bib8] [8] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Sublinear time algorithms and complexity of approximate maximum matching. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 267–280. ACM, 2023. doi:10.1145/3564246.3585231.

[bib.bib9] [9] Andrew Beveridge, Alan Frieze, and Colin McDiarmid. Random minimum length spanning trees in regular graphs. Combinatorica, 18(3):311–333, 1998. doi:10.1007/PL00009825.

[bib.bib10] [10] Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. Beyond worst case local computation algorithms. arXiv preprint, 2025. arXiv:2403.00129.

[bib.bib11] [11] Greg Bodwin and Henry Fleischmann. Spanning adjacency oracles in sublinear time, 2024.

[bib.bib12] [12] Béla Bollobás, Yoshiharu Kohayakawa, and Tomasz Łuczak. The evolution of random subgraphs of the cube. Random Structures & Algorithms, 3(1):55–90, 1992. doi:10.1002/RSA.3240030106.

[bib.bib13] [13] Christian Borgs, Michael Brautbar, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier. The power of local information in social networks. In International Workshop on Internet and Network Economics, pages 406–419. Springer, 2012. doi:10.1007/978-3-642-35311-6_30.

[bib.bib14] [14] Michael Brautbar and Michael J Kearns. Local algorithms for finding interesting individuals in large networks, 2010.

[bib.bib15] [15] SR Broadbent and JM Hammersley. Percolation processes. i. crystals and mazes. Cambridge Philos. Soc. Math. Proc., 53:629–641, 1957.

[bib.bib16] [16] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of ( $\delta$ + 1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 471–480, 2019. doi:10.1145/3293611.3331607.

[bib.bib17] [17] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on computing, 34(6):1370–1379, 2005. doi:10.1137/S0097539702403244.

[bib.bib18] [18] Fan Chung, Paul Horn, and Linyuan Lu. Percolation in general graphs. Internet Mathematics, 6(3):331–347, 2009. doi:10.1080/15427951.2009.10390644.

[bib.bib19] [19] Artur Czumaj, Yishay Mansour, and Shai Vardi. Sublinear graph augmentation for fast query implementation. In International Workshop on Approximation and Online Algorithms, pages 181–203. Springer, 2018. doi:10.1007/978-3-030-04693-4_12.

[bib.bib20] [20] Sahar Diskin and Michael Krivelevich. Expansion in supercritical random subgraphs of expanders and its consequences. Random Structures & Algorithms, 65(3):576–600, 2024. doi:10.1002/RSA.21225.

[bib.bib21] [21] Paul Erd6s and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17–61, 1960.

[bib.bib22] [22] Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In European Symposium on Algorithms, pages 394–405. Springer, 2014. doi:10.1007/978-3-662-44777-2_33.

[bib.bib23] [23] Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.50.

[bib.bib24] [24] Alan Frieze and Tony Johansson. On edge-disjoint spanning trees in a randomly weighted complete graph. Combinatorics, Probability and Computing, 27(2):228–244, 2018. doi:10.1017/S0963548317000426.

[bib.bib25] [25] Alan Frieze, Michael Krivelevich, and Ryan Martin. The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Structures & Algorithms, 24(1):42–50, 2004. doi:10.1002/RSA.10100.

[bib.bib26] [26] Alan Frieze and Wesley Pegden. Looking for vertex number one. The Annals of Applied Probability, pages 582–630, 2017.

[bib.bib27] [27] Alan M Frieze. On the value of a random minimum spanning tree problem. Discrete Applied Mathematics, 10(1):47–56, 1985. doi:10.1016/0166-218X(85)90058-7.

[bib.bib28] [28] Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 270–277. SIAM, 2016. doi:10.1137/1.9781611974331.CH20.

[bib.bib29] [29] Mohsen Ghaffari. Local computation of maximal independent set. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 438–449. IEEE, 2022. doi:10.1109/FOCS54457.2022.00049.

[bib.bib30] [30] Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1636–1653. SIAM, 2019. doi:10.1137/1.9781611975482.99.

[bib.bib31] [31] Avinatan Hassidim, Jonathan A Kelner, Huy N Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 22–31. IEEE, 2009. doi:10.1109/FOCS.2009.77.

[bib.bib32] [32] Jane Lange, Ephraim Linder, Sofya Raskhodnikova, and Arsen Vasilyan. Local lipschitz filters for bounded-range functions with applications to arbitrary real-valued functions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2881–2907. SIAM, 2025. doi:10.1137/1.9781611978322.93.

[bib.bib33] [33] Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan. Properly learning monotone functions via local correction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 75–86. IEEE, 2022. doi:10.1109/FOCS54457.2022.00015.

[bib.bib34] [34] Jane Lange and Arsen Vasilyan. Agnostic proper learning of monotone functions: beyond the black-box correction barrier. SIAM Journal on Computing, pages FOCS23–1, 2025.

[bib.bib35] [35] Jane Lange and Arsen Vasilyan. Robust learning of halfspaces under log-concave marginals. arXiv preprint, 2025. doi:10.48550/arXiv.2505.13708.

[bib.bib36] [36] Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 87:1–87:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.87.

[bib.bib37] [37] Reut Levi, Moti Medina, and Omer Tubul. Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), volume 317 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1–60:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.60.

[bib.bib38] [38] Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, and Asaf Shapira. Constructing near spanning trees with few local inspections. Random Structures & Algorithms, 50(2):183–200, 2017. doi:10.1002/RSA.20652.

[bib.bib39] [39] Reut Levi and Dana Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms (TALG), 11(3):1–13, 2015. doi:10.1145/2629508.

[bib.bib40] [40] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, page 826, 2014.

[bib.bib41] [41] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. Algorithmica, 82(4):747–786, 2020. doi:10.1007/S00453-019-00612-6.

[bib.bib42] [42] Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica, 77(4):971–994, 2017. doi:10.1007/s00453-016-0126-y.

[bib.bib43] [43] Reut Levi and Nadav Shoshan. Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.61.

[bib.bib44] [44] Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 260–273. Springer, 2013. doi:10.1007/978-3-642-40328-6_19.

[bib.bib45] [45] Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local computation algorithms for spanners. Innovations in Theoretical Computer Science (ITCS), 2019.

[bib.bib46] [46] Pan Peng and Yuyang Wang. Local computation algorithms for (minimum) spanning trees on expander graphs, 2026. doi:10.48550/arXiv.2602.07394.

[bib.bib47] [47] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 223–238. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/36.html.

[bib.bib48] [48] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and computation, 82(1):93–133, 1989. doi:10.1016/0890-5401(89)90067-9.

[bib.bib49] [49] J Michael Steele. Minimal spanning trees for graphs with random edge lengths. In Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, pages 223–245. Springer, 2002.

[bib.bib50] [50] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An improved constant-time approximation algorithm for maximum matchings. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 225–234, 2009. doi:10.1145/1536414.1536447.

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Basic Definitions

Definition 1.1 (Local Computation Algorithm).

Definition 1.2 (LCA for (Minimum) Spanning Tree).

Definition 1.3 (Average-case LCA).

1.2 Our Results

Spanning Trees in Expanders

Theorem 1.4.

Spanning Trees in Erdős-Rényi Graphs

Theorem 1.5.

Minimum Spanning Tree

Theorem 1.6.

1.3 Technical Overview

1.3.1 Spanning Tree in Expander Graphs

Global Algorithm Overview

Local Algorithm Implementation

1.3.2 Spanning Tree in Random Graphs

Beyond the 𝒏 Barrier

Proof Techniques

1.3.3 Minimum Spanning Tree

Hierarchy by Random Weights

Unweighted Spanning Tree for Reference

1.4 Other Related Work

LCA for Sparse Spanning Subgraphs (Spanners)

LCA for Other Problems

Average-Case LCA

Phase Transition of Random Subgraphs

MSTs on Graphs with Randomly Assigned Edge Weights

2 Preliminaries

Definition 2.1.

Definition 2.2 (path).

Definition 2.3 (path ordering).

Definition 2.4 (lexicographically-least shortest path).

Definition 2.5 (Erdős-Rényi graphs).

2.1 Access Models

Adjacency List Model.

General Graph Model.

2.2 Searching for the Lexicographically-Least Shortest Path

2.3 Conductance, Expander graphs and Random walks

Definition 2.6 (conductance).

Corollary 2.7 ([37]).

3 LCA for Spanning Tree on Expanders

3.1 A Global Algorithm for Constructing Spanning Trees

Definition 3.1 (anchor).

3.1.1 Correctness of Algorithm 1

Theorem 3.2.

Lemma 3.3.

Proof.

Proof of Theorem 3.2.

3.2 Local Implementation

Claim 3.4.

Proof.

Lemma 3.5.

Proof.

3.3 Probe Complexity of the LCA

Lemma 3.6.

Proof.

Claim 3.7.

Proof.

Lemma 3.8.

Proof.

3.4 Proof of Theorem 1.4

Proof.

References

Beyond the $\sqrt{n}$ Barrier