betaFeedback

WorksComputer Science

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give n1/2+o(1)n^{1/2+o(1)}-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor n1/3+o(1)n^{1/3+o(1)}, with high probability, in O~(m+n)\widetilde{O}(m+n) time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an n2/15−εn^{2/15-\varepsilon}-approximation in O~(m+n)\widetilde{O}(m+n) time for every fixed ε∈(0,2/15)\varepsilon\in(0,2/15), establishing the necessity of polynomial loss for nearly-linear time algorithms.

Introduction

The reachability diameter of a graph is the maximum uu-to-vv shortest-path distance across all pairs u,vu,v such that vv is reachable from uu. It coincides with the classic notion of diameter whenever every vertex can reach every other vertex. Otherwise, the classical diameter is infinite, potentially obscuring the distances between pairs that remain reachable. For example, adding a single isolated vertex to a connected undirected graph makes its classical diameter infinite without changing any distances between the original vertices. Similarly, deleting one edge of a directed cycle produces a directed path: its classical diameter becomes infinite, but its reachability diameter remains unchanged. Thus, reachability diameter generalizes classical diameter in applications where finite distances are more informative than infinite ones. The reachability diameter is also the relevant quantity in the shortcut set problem, where the goal is to efficiently construct a sparse set of reachability-preserving edges, which are added to the input digraph to reduce its reachability diameter to a prescribed hopbound (each edge a hop). Despite this, it has received much less attention as a computational problem in its own right.

Bals, Blikstad, Dadush, Nazari, and Schmidt [3] pioneered the study of efficiently estimating this quantity in unweighted digraphs. Throughout, nn and mm denote respectively the numbers of vertices and edges, and a ρ\rho-approximation to the reachability diameter DD is an estimate D^\widehat{D} satisfying D/ρ≤D^≤DD/\rho\leq\widehat{D} \leq D. They give an n1/2+o(1)n^{1/2+o(1)}-approximation algorithm running in nearly-linear O~(m+n)\widetilde{O}(m+n) time, yet surprisingly their conditional hardness results only rule out approximation factors below certain constants. Specifically, the Boolean matrix multiplication (BMM) hypothesis rules out combinatorial better-than-2 approximations in truly subcubic time, while the orthogonal vectors (OV) hypothesis rules out better-than-3/2 approximations in truly subquadratic time, even on sparse graphs. In matrix-multiplication time they show that exact computation is already possible. By contrast, assuming ω>2\omega> 2, the simplicial vertex hypothesis (SV) rules out any polynomial-factor approximation in near-linear time in the weighted regime (Table 1). We focus on the near-linear time regime, improving both the approximation guarantee and the conditional hardness bound.

UndirectedDirected
Unweightedupper<br>2 [7]<br><br>lower<br>3/2−ε3/2-\varepsilon [18] (OV)upper<br>prior: n1/2+o(1)n^{1/2+o(1)} [3]<br>ours: n1/3+o(1)n^{1/3+o(1)}<br><br>lower<br>prior: 3/2−ε3/2-\varepsilon [3] (OV)<br>ours: n2/15−εn^{2/15-\varepsilon} (HC)
Weightedupper<br>2 [7]<br><br>lower<br>3/2−ε3/2-\varepsilon [18] (OV)upper<br>—<br><br>lower<br>ncn^c (all c>0c>0) [3] (SV)1

Table 1. Reachability diameter approximation in near-linear time. Upper bounds correspond to O~(m+n)\widetilde{O}(m+n)-time algorithms, lower bounds mean an approximation factor is excluded under the listed hypothesis, for fixed ε>0\varepsilon>0. For randomized HC the bound holds for algorithms with at least 2/32/3 success rate.

The n1/2n^{1/2} barrier. The n1/2+o(1)n^{1/2+o(1)}-approximation algorithm of Bals et al. [3] inherits its approximation factor from the hopbound of the underlying shortcut algorithm, which seeks to efficiently match a well known folklore construction achieving a O~(n1/2)\widetilde{O}(n^{1/2}) hopbound. Improving the approximation factor requires going beyond what this hopbound directly implies. We recall the construction: given an input unweighted digraph, sample ⌈n1/2⌉\lceil n^{1/2}\rceil vertices called pivots uniformly at random without replacement. Run BFS from each pivot ss and include the edge (s,s′)(s,s') for each other pivot s′s' reachable from ss. Fix one shortest path for each ordered pair of vertices with finite distance. Then every sufficiently long such path contains a pivot near each endpoint with high probability, allowing the segment between them to be traversed in a single hop via the associated shortcut edge. With ⌈n1/2⌉\lceil n^{1/2}\rceil pivot samples the construction adds only O(n)O(n) edges, and the reachability diameter of the augmented graph is bounded by O~(n1/2)\widetilde{O}(n^{1/2}).

To see how estimating reachability diameter inherits the folklore n1/2n^{1/2} barrier, consider a simple modification of the folklore algorithm: whenever a BFS is initiated at a pivot, record the largest depth seen during the search. In the trivial case, output 0, otherwise report the maximum of 1 and the recorded depths, and retain the shortcut set constructed along the way for the analysis. This already yields a O~(n1/2)\widetilde{O}(n^{1/2})-approximation to the reachability diameter. To see why, condition on the high-probability event described above, and let PP be a fixed diametral path. The construction partitions PP into at most O~(n1/2)\widetilde{O}(n^{1/2}) segments, each consisting of either a single original edge or a subpath whose endpoints are joined by a shortcut. By an application of the pigeon-hole principle, some segment has length Ω~(D/n1/2)\widetilde{\Omega}(D/n^{1/2}). If this segment corresponds to a shortcut edge (s,s′)(s,s'), BFS initiated at ss reports the distance exactly. The limitation of this approach is the cost of search, yielding an O((m+n)n)O((m+n)\sqrt{n}) running time, which exceeds our near-linear time target. Efficient shortcut constructions would offer a route to a comparable approximation guarantee for estimating reachability diameter in the desired near-linear time.

History of efficient shortcut construction. The challenge of constructing sparse shortcut sets efficiently has long been central to parallel reachability, the problem of finding all vertices reachable from a given source. Parallel BFS explores each layer concurrently, which can require as many sequential rounds as its reachability diameter. Motivated by parallel reachability, Thorup [21] formalized the problem of reducing a digraph’s reachability diameter by adding a set of reachability-preserving edges. The construction must be efficient, and the shortcut set sparse, to retain the near-linear total computational cost of BFS. The first shortcut-set algorithm achieving, with high probability, polynomially sublinear O~(n2/3)\widetilde{O}(n^{2/3}) reachability diameter with O~(m)\widetilde{O}(m) running time and O~(n)\widetilde{O}(n) size was discovered by Fineman [9], refining the sample and search approach of Ullman and Yannakakis [22].

Soon after, Jambulapati, Liu, and Sidford [13] obtained the first efficient and sparse construction (JLS algorithm) whose bound O(n1/2+o(1))O(n^{1/2+o(1)}) nearly matches the folklore algorithm’s. For a fixed path PP, instead of a pivot near each endpoint being used to shortcut the middle segment, the JLS algorithm partitions the graph, which fragments PP, and constructs a shortcut for each fragment. At every recursive level its fragments are either resolved by being shortcut through a sampled pivot, or become recursive subproblems, further subdivided and eventually shortcut with later samples. The expected number of fragments of PP over the course of the recursion is at most n1/2+o(1)n^{1/2+o(1)}. It is at this point that shortcut construction meets diameter estimation. Bals et al. [3] show that the JLS algorithm’s partitioning preserves original graph distances in each child, and by an application of the triangle inequality, search from pivots reveals a distance at least half the length of fragments of shortest paths which they resolve. Combining these ideas and the prior pigeon-hole argument, they achieve the first n1/2+o(1)n^{1/2+o(1)}-approximation reachability diameter algorithm in unweighted digraphs. By tying the approximation factor to the shortcut hopbound, the approach of Bals et al. carries the folklore n1/2n^{1/2} benchmark into reachability diameter estimation, making it an apparent barrier for this problem as well.

Further developments in shortcut sets emphasize n1/2n^{1/2} as a significant benchmark. Kogan and Parter achieve a substantially smaller hopbound of O~(n1/3)\widetilde{O}(n^{1/3}) [15], but their construction takes superlinear O~(mn1/3)\widetilde{O}(mn^{1/3}) time [16]. Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak [2] retain near-linear work and improve the reachability diameter to (nω+o(1)m)1/(2ω−2)\left(\frac{n^{\omega+o(1)}}{m}\right)^{1/(2\omega-2)} on dense graphs allowing O~(m)\widetilde{O}(m) shortcut edges, where ω\omega is the matrix multiplication exponent. However, their guarantee remains n1/2+o(1)n^{1/2+o(1)} on sparse graphs. This motivates the following refinement of the question of [3]:

Problem 1. Can reachability diameter estimation overcome n1/2n^{1/2} in better-than-matrix-multiplication time, without a corresponding improvement in shortcut construction?

We answer this question in the affirmative, giving a randomized O~(m+n)\widetilde{O}(m+n)-time algorithm that achieves an n1/3+o(1)n^{1/3+o(1)}-approximation with high probability.

Theorem 1. There is a randomized algorithm computing a n1/3+o(1)n^{1/3+o(1)}-approximation to the reachability diameter of an unweighted digraph with high probability, running in O~(m+n)\widetilde{O}(m+n) time.

Our algorithm builds on the same recursive partitioning framework of Jambulapati et al. [13] also used by Bals et al. Following a fixed diametral path, at each level of the recursion random samples either further subdivide an existing fragment, or resolve it entirely. Bals et al. show that resolved fragments reveal distances in the base input graph, and thus the final count of resolved fragments controls the approximation ratio of their algorithm. In contrast, with careful analysis we show that our approach obtains a measurement earlier in the recursion, before repeated decompositions have cut the length of the diametral path into too many pieces. The difficulty lies in detecting a sufficiently long piece when it is unresolved. To address this, we adapt a randomized procedure of Cohen [5] for estimating the size of a neighborhood to finding length-witnesses of unresolved pieces. Our analysis balances bounds of Ashvinkumar et al. [2] on the number of large recursive subproblems, with the success rate of the adapted procedure, breaking the n1/2n^{1/2} approximation barrier for reachability diameter. The algorithm and proof are given in § 4.

Polynomial approximation loss. Beyond breaking the n1/2n^{1/2} barrier, the broader question of Bals et al. [3] leaves open whether a constant-factor approximation is possible in near-linear time. They suggest approaching this problem from the other direction, proving a stronger lower bound, a route which is especially compelling when comparing the approximation landscape for weighted and unweighted digraphs Table 1. Recall that the reachability diameter measures the maximum finite distance between vertices of a digraph, which coincides in the undirected setting with the maximum classic diameter of a connected component. In the undirected setting: applying well-known folklore algorithms to each connected component already gives a 2-approximation in near-linear time to

the reachability diameter in both weighted and unweighted graphs. Surprisingly, the picture is dramatically different in the directed setting: in the weighted regime, assuming ω>2\omega>2 and the simplicial vertex hypothesis (SV), Bals et al. [3] rule out every polynomial approximation factor in near-linear time. Yet switching to the unweighted regime changes the picture again. Bals et al. obtain a polynomial-factor approximation in near-linear time, while their conditional lower bounds exclude only approximation factors below certain constants. This motivates the following question:

Problem 2. Does reachability diameter in unweighted digraphs admit a constant-factor, or more generally a subpolynomial-factor, approximation in near-linear time?

Our result closes this question under the 3-uniform Hyperclique hypothesis (HC). We show that polynomial approximation loss is unavoidable, although the optimal polynomial exponent remains open.

Theorem 2. Assume the deterministic 3-uniform Hyperclique hypothesis. For every fixed ε∈(0,2/15)\varepsilon\in(0,2/15), there is no deterministic O~(n+m)\widetilde{O}(n+m)-time algorithm that, on every unweighted digraph GG with nn vertices, mm edges, and reachability diameter DD, returns an estimate satisfying

Dn2/15−ε≤D^≤D.\frac{D}{n^{2/15-\varepsilon}}\le\widehat{D}\le D.

Under the randomized version of the hypothesis, there is no randomized O~(n+m)\widetilde{O}(n+m)-time algorithm that, on every input graph, returns an estimate satisfying this guarantee with probability at least $2/3.

One particular difficulty raised by Bals et al. [3] is the “triangle-inequality barrier” [1, 14, 19]. To establish a large approximation lower bound, a reduction must produce a large gap in diameter: one case must contain a pair of vertices far apart, while the other must keep every reachable pair close. The “triangle-inequality barrier” obstructs the natural approach of creating a long path and selectively shortcutting its endpoints: intermediate vertices may remain far apart even after the shortcut is added, leaving both cases with large diameter. Our reduction encodes a hyperclique candidate by a constant-direction trajectory in a layered DAG, and adds short channels that compress trajectories encoding candidates that violate a hyperclique constraint. When no hyperclique exists, every reachable pair can be connected through a small number of the compressed trajectory segments. An energy coordinate preserves a long distance when a hyperclique does exist, preventing any detours. Finally, a Chinese remainder encoding keeps these channels small enough. Balancing the resulting trade-off between graph size and the diameter gap yields the exponent 2/15−ε2/15-\varepsilon. The construction and proof are given in § 3.

AI Disclosure

ChatGPT 6 and 6.1 models contributed the majority of the results, and assisted with drafting and revision. The authors rewrote all model-generated prose; the final wording is entirely their own.

Technical Overview

Preliminaries

Let G=(V,E)G=(V,E) be the input unweighted digraph, with n=∣V∣n=|V| vertices and m=∣E∣m=|E| edges. Our algorithm proceeds by recursive partitioning; to differentiate the base input graph from the input to an arbitrary recursive subproblem we write H=(V(H),E(H))H=(V(H),E(H)) for the latter, where HH is a subgraph of GG.

For u,v∈Vu,v\in V, the function d(u,v)d(u,v) is the shortest-path distance in GG, even when uu and vv belong to a recursive subproblem. In particular, d(u,v)=∞d(u,v)=\infty when there is no directed uu-to-vv path in GG, and d(u,u)=0d(u,u)=0. For a dipath PP, we denote by P[V(H)]P[V(H)] the restriction of PP to V(H)V(H). When P=(ustart,…,uend)P=(u_{\mathrm{start}},\ldots,u_{\mathrm{end}}) is a shortest dipath in GG, we use d(P)d(P) to refer to the endpoint to endpoint distance d(ustart,uend)d(u_{\mathrm{start}},u_{\mathrm{end}}).

In any recursive instance with input HH and u,v∈V(H)u,v\in V(H), we write u⇝Hvu\leadsto_H v when there exists a directed uu-to-vv path through HH, including dipaths consisting of a single vertex, so u⇝Huu\leadsto_H u. When the relevant graph is clear from context, we simply say u⇝vu\leadsto v. The out-relevance RH+(u)={v∈V(H)∣u⇝v}R_H^+(u)=\{v\in V(H)\mid u\leadsto v\} of uu, also called the descendants of uu in HH, is the subset of V(H)V(H) which is reachable from uu, or equivalently, the set of vertices discovered during BFS initiated at uu on HH. Symmetrically, the in-relevance (ancestors) of uu in HH, RH−(u)={v∈V(H)∣v⇝u}R_H^-(u)=\{v\in V(H)\mid v\leadsto u\}, is the set of vertices discovered during reverse BFS: BFS with all edge directions reversed. The union RH(u)=RH+(u)∪RH−(u)R_H(u)=R_H^+(u)\cup R_H^-(u) is called the relevance. The size, or cardinality of these sets is denoted: ∣RH+(u)∣,∣RH−(u)∣,∣RH(u)∣|R_H^+(u)|,|R_H^-(u)|,|R_H(u)|. For a dipath P=(u1,…)P=(u_1,\ldots) lying in HH, the relevance is RH(P)=⋃iRH(ui)R_H(P)=\bigcup_iR_H(u_i), and similarly we have: RH−(P)=⋃iRH−(ui)R_H^-(P)=\bigcup_iR_H^-(u_i), and RH+(P)=⋃iRH+(ui)R_H^+(P)=\bigcup_iR_H^+(u_i). When V′⊆V(H)V'\subseteq V(H) is a set of vertices, H[V′]H[V'] is the subgraph of HH induced by V′V'.

Lower Bound

Polynomial approximation loss. The existing lower bounds for unweighted reachability diameter, based on Boolean matrix multiplication and Orthogonal Vectors, establish constant-factor approximation barriers [3]. These results leave open whether a larger constant factor, or even a polylogarithmic factor, can be achieved in near-linear time. In comparison, the approximation guarantees of known near-linear-time algorithms, including ours, still grow polynomially with nn. This leaves a basic question: is some polynomial approximation loss necessary, or can further algorithmic improvements eliminate it? We seek a conditional lower bound showing that approximation within a fixed positive power of nn already requires more than near-linear time. Such a bound would establish that polynomial approximation loss is inherent under the hypothesis, while leaving the optimal exponent open. Our lower bound result is built on the following 3-uniform Hyperclique hypothesis.

A hypergraph allows an edge to contain more than two vertices, which is called as a hyperedge. In a 3-uniform hypergraph, every hyperedge consists of exactly three vertices. We consider a KK-partite hypergraph whose vertex set is partitioned into KK disjoint parts V1,…,VKV_1,\ldots,V_K, each containing NN vertices. Every hyperedge contains vertices from three distinct parts. A KK-hyperclique is a set of KK vertices, one from each part, such that every three vertices in the set form a hyperedge.

Hypothesis 1 (3-uniform Hyperclique Hypothesis [17]). For every fixed integer K≥4K \ge4 and constant η>0\eta> 0, there is no deterministic algorithm deciding whether a 3-uniform KK-partite hypergraph with NN vertices in each part has a KK-hyperclique in O(NK−η)O(N^{K-\eta}) time. The randomized version asserts the same for randomized algorithms with error probability at most 1/31/3 on every input.

Label the vertices in each part by [N]:={0,…,N−1}[N] := \{0,\ldots,N-1\}, and let Xr∈[N]X_r \in[N] specify the vertex selected from VrV_r. Consider any three vertices v1,v2,v3v_1,v_2,v_3 from distinct parts Vr1,Vr2,Vr3V_{r_1},V_{r_2},V_{r_3} that do not form a hyperedge. Since a KK-hyperclique cannot contain all three vertices, we impose the constraint ¬(Xr1=v1∧Xr2=v2∧Xr3=v3)\neg(X_{r_1}=v_1 \land X_{r_2}=v_2 \land X_{r_3}=v_3). Let C\mathcal{C} be the collection of all constraints obtained in this way. Then ∣C∣≤(K3)N3|\mathcal{C}| \le\binom{K}{3}N^3. Trivially, we have

a hyperclique exists⟺some assignment violates no constraint,\text{a hyperclique exists} \Longleftrightarrow\text{some assignment violates no constraint,}
no hyperclique exists⟺every assignment violates at least one constraint.\text{no hyperclique exists} \Longleftrightarrow\text{every assignment violates at least one constraint.}

Choosing the hypothesis. Our choice of the Hyperclique hypothesis is motivated by a connection between reachability diameter and geometric coverage. A small reachability diameter means that short paths connect every reachable pair, while a large reachability diameter witnesses a failure of this property. This resembles geometric coverage, where the question is whether a collection of objects covers an entire region or leaves an uncovered point. Hyperclique-based lower bounds for Klee’s measure problem exploit precisely this distinction: complete coverage corresponds to the absence of a hyperclique [17].

In this analogy, an uncovered point corresponds to a reachable pair whose distance remains large. The related shortcutting problem asks whether adding a small set of reachability-preserving edges can make every reachable pair close. Shortcut lower bounds show that making all reachable pairs close can face a polynomial obstruction [12]. We ask whether detecting a remaining long distance also faces a polynomial approximation barrier in near-linear time. The Hyperclique hypothesis provides a natural starting point for connecting the computational hardness of global coverage with the structural obstacles identified by shortcut lower bounds.

Constructing the graph. Our goal is to construct a digraph substantially faster than enumerating the NKN^K candidates, with a large reachability diameter if and only if a hyperclique exists. Our digraph is built on geometric constructions used in shortcut and distance-preserver lower bounds [4, 6, 11, 12]. We assign integer coordinates to vertices and arrange them in layers, with all edges directed from earlier layers to later layers. Thus, the graph is a DAG and Theorem 2 also applies to DAGs. Each trajectory follows a fixed direction across the layers and encodes a candidate assignment to X1,…,XKX_1,\ldots,X_K. We connect its vertices in consecutive layers by constant-length dipaths. If the encoded assignment violates a constraint in CC, we also add shortcuts that cross many layers using only a constant number of edges to force short distances.

Protecting a satisfying assignment. The main difficulty is to ensure that shortcuts for failing assignments do not also shorten distances associated with a satisfying assignment. Earlier shortcut and distance-preserver lower bounds choose movement vectors so that none is a weighted average of the others [6, 11, 12]. We adapt this convexity argument using an energy coordinate. More specifically, each move between consecutive layers increases this coordinate by the squared Euclidean norm of its direction, and each shortcut contributes the total increase of the moves it replaces.

Consider different sequences of moves that cross the same number of layers and produce the same total change in the spatial coordinates. Moving in a constant direction gives the smallest total energy increase. Any sequence that changes direction requires a strictly larger energy increase. This comparison is closely related to the use of squared movement costs to exclude alternative shortest paths in Bodwin and Hoppenworth [4 Section 4.4, Proposition 3 and Lemma 2]. We set the energy difference between vertices on a trajectory to this minimum. Any dipath connecting them must therefore preserve the trajectory’s direction and cannot use shortcuts for a different assignment. Consequently, a satisfying assignment retains a distance proportional to the number of layers.

Upper Bound

Our algorithm builds on the recursive partitioning framework of Jambulapati, Liu, and Sidford [13]. We call the following recursive sampling, searching, labelling, and grouping procedure JLS partitioning.

JLS partitioning. Let HH be the input to an arbitrary instance at level rr of the recursion, where the root instance GG is at level r=0r=0.

  • Sampling: Sample pivots SS from V(H)V(H) uniformly at random with probability prp_r. The sampling probability grows by Θ(log⁡n)\Theta(\log n) per recursion level, so after O(log⁡n)O(\log n) levels pr=1p_r=1 and every remaining vertex becomes a pivot.

  • Search: Run BFS and reverse BFS from each s∈Ss \in S. Remove all vertices found in both search directions initiated at a pivot.

  • Labelling: Each pivot ss assigns every v∈V(H)v \in V(H) a reachability signature

σs(v):=(1[v⇝s],1[s⇝v]).\sigma_s(v) := \bigl(\mathbf{1}[v \leadsto s],\mathbf{1}[s \leadsto v]\bigr).

where 1[⋅]\mathbf{1}[\cdot] denotes the indicator function.

  • Grouping: Group the remaining vertices into sets V1,…V_1,\ldots according to their reachability signatures. The induced subgraphs H[V1],…H[V_1],\ldots are the inputs to the recursive children of HH.

We now make precise what it means to resolve a dipath fragment. To complete the construction of Jambulapati et al. [13], for each pair consisting of a recursive input HH and an associated pivot ss add the following edges to the shortcut set:

(i) (u,s) for every u∈RH−(s),(ii) (s,v) for every v∈RH+(s).\mathrm{(i)}\ (u,s)\ \text{for every }u\in R_H^{-}(s),\qquad \mathrm{(ii)}\ (s,v)\ \text{for every }v\in R_H^{+}(s).

These edges preserve reachability by definition. Now fix some instance with input HH and pivot samples S⊆V(H)S \subseteq V(H). Let PP be any uu-to-vv dipath in HH, u,v∈V(H)u,v \in V(H). A pivot ss is called a bridge of PP when u⇝su \leadsto s and s⇝vs \leadsto v. If such a pivot exists, then the shortcut edges (u,s)(u,s) and (s,v)(s,v) reduce the shortest uu-to-vv distance to at most two hops in the augmented graph. We therefore regard PP as resolved for the shortcut construction. In particular, vertices removed during the search phase are mutually reachable with a sampled pivot, which bridges any path fragments consisting of those vertices. After O(log⁡n)O(\log n) levels, the sampling probability satisfies pr=1p_r = 1 and every remaining vertex is sampled as a pivot, including every vertex lying on every remaining path, thereby resolving them.

From shortcuts to detecting distances. Bals et al. [3] connect resolving a shortest-path fragment with detecting a large distance in the original graph through the following structural guarantees of JLS partitioning.

Lemma 1 (Adapted from Lemma 22 and Corollary 23 of Bals et al. [3]). Let GG be an unweighted digraph, and let HH be the input to any recursive instance obtained from GG by repeated JLS partitioning. Then:

  • For every directed path PP in GG, the restriction P[V(H)]P[V(H)] is either empty or consists of a contiguous subpath of PP.

  • For every u,v∈V(H)u,v \in V(H), the shortest-path distance from uu to vv in HH equals d(u,v)d(u,v), their shortest-path distance in GG.

Proof. The base case H=GH = G is immediate. Now suppose that an arbitrary instance with input HH satisfies both given statements. We proceed by induction on the recursive subproblems H[V1],…H[V_1], \ldots. By way of contradiction, suppose that u,v,w∈V(H)u,v,w \in V(H), all different, such that there is a uu-to-vv directed path in HH containing ww, but after partitioning ww end up in a different child than u,vu,v: u,v∈Viu,v \in V_i and w∉Viw \notin V_i. The case where ww is dropped after the searching phase is immediate, if there exists some pivot such that ww is found in both of its search directions then uu and vv are also found in both searches, and dropped. Since uu and vv belong to the vertices of the same child they have identical reachability signatures. Meaning that, for every sampled pivot s∈Ss \in S, we have s⇝u⇒s⇝w⇒s⇝vs \leadsto u \Rightarrow s \leadsto w \Rightarrow s \leadsto v and v⇝s⇒w⇝s⇒u⇝sv \leadsto s \Rightarrow w \leadsto s \Rightarrow u \leadsto s. These implications force uu and vv to have exactly the same labels as ww, a contradiction. Thus, for every ordered pair of endpoints that are grouped into the same recursive child, every vertex on every dipath connecting them in HH is grouped into the same child. By induction, every directed path PP in HH, the restriction P[Vi]P[V_i] is either empty or consists of a contiguous subpath of PP. Moreover, for every u,v∈Viu,v \in V_i, the shortest-path distance from uu to vv in H[Vi]H[V_i] equals d(u,v)d(u,v), their shortest-path distance in GG. □\square

Observation 1 (Observation 21 and Corollary 23 of Bals et al. [3]). Let GG and HH be as in Lemma 1. Then for u,v∈V(H)u,v \in V(H), the shortest-path distance from uu to vv in HH equals their shortest-path distance in GG. In other words, if d(u,v)d(u,v) is finite, then HH contains some uu-to-vv dipath PP of length d(u,v)d(u,v). Fix some such u,vu,v, and suppose that we sample a bridge ss of PP in the recursive instance corresponding to input HH, so u⇝su \leadsto s and s⇝vs \leadsto v. By another application of Lemma 1, BFS and reverse BFS from ss in the search phase of JLS partitioning reveal d(u,s)d(u,s) and d(s,v)d(s,v). The triangle inequality gives: d(u,v)/2≤max⁡(d(u,s),d(s,v))≤Dd(u,v)/2 \le\max(d(u,s),d(s,v)) \le D. Thus, resolving PP reveals a distance at least half its length, without overestimating the reachability diameter of GG.

This observation explains how Bals et al. acquire distance estimates from resolved fragments, inheriting the n1/2+o(1)n^{1/2+o(1)} bound of the underlying shortcut analysis. Our approach seeks to obtain an estimate during the earlier stages of the JLS partitioning, while fragments of diametral paths retain more of their length. However, stopping earlier in the analysis requires a method to detect distances in unresolved fragments, for which the argument of Observation 1 provides no guarantee.

Detecting distances in unresolved fragments. For unresolved path fragments, our algorithm adapts a procedure of Cohen used for estimating the sizes of reachability sets (Algorithm 3.1 of [5]). The general description of the algorithm is as follows: process the vertices of an input digraph in a uniformly random order, using reverse BFS to identify their least-rank descendants. The idea is that vertices with larger out-relevance sets expect to see their first descendant earlier in the ordering, so the minimum rank of its descendants in the ordering informs an estimate of the size of the out-relevance.

Cohen also establishes that the choice of least-descendant is distributed uniformly at random over the associated out-relevance set (Propositions 2.1-2.2 of [5]). Our Sweep subroutine exploits this fact in the symmetric procedure, which identifies the least-rank ancestor, to detect distances in unresolved fragments.

Algorithm 1 Sweep(HH).

Input: Recursive instance HH.

Output: An original distance in the base input graph to ReachDiam.

  1. Process the initially uncolored vertices V(H)V(H) in a uniformly random order. When an uncolored vertex is encountered: start BFS with it as the root, then color and remove every vertex discovered by the search (in the working graph only).

  1. Report the largest distance observed during any search.

As in Cohen’s procedure, each vertex is colored by the search rooted at its first ancestor encountered during processing, its least-rank ancestor in HH.

To see why Sweep works to detect distance in unresolved fragments: let HH be the input to any recursive instance obtained from GG by repeated JLS partitioning, such that HH contains a shortest dipath P=(p1,…,pk)P = (p_1,\ldots,p_k) with in-relevance RH−(P)R_H^-(P). Suppose that we do not sample a bridge of PP in the current instance, i.e. PP is unresolved in this exercise. First, we naturally extend the definition of least-rank ancestor to dipaths PP as the first ancestor of any of its vertices encountered during processing. In particular, Propositions 2.1-2.2 of [5] still apply: the least-rank ancestor aa of PP is distributed uniformly at random over RH−(P)R_H^-(P). Additionally, aa and every vertex of PP are uncolored at the moment when aa is encountered in the ordering, otherwise we must have already processed an ancestor of PP, a contradiction with aa’s minimality. Now consider the event that aa is one of the vertices p1,…,p⌊k/2⌋p_1,\ldots,p_{\lfloor k/2\rfloor} lying on the first half of PP, called witnesses. Then BFS rooted at aa reveals the length of the aa-to-pkp_k subpath of PP, which is at least half the length of PP. By Lemma 1, the length of PP in HH is equal to the shortest-path distance d(p1,pk)d(p_1,p_k) in GG, thus Sweep reports at least half the length of the unresolved path fragment. Moreover, Sweep does not overestimate. After each search the colored set is closed under reachability in HH, and therefore all paths between uncolored vertices are themselves uncolored, meaning that BFS distances reported by Sweep equal their distances in HH, hence GG. Then, conditioned on the event described above, Sweep reports an original distance in the input at least half the length of the unresolved path fragment.

Moreover, the choice of aa is uniformly random over RH−(P)R_H^-(P), so the probability that aa lies on the first half of PP is exactly the ratio of the number of witnesses p1,…,p⌊k/2⌋p_1,\ldots,p_{\lfloor k/2\rfloor}, to the total size of PP’s in-relevance in HH.

Controlling the ratio of witnesses. The analysis of JLS partitioning by Ashvinkumar et al. [2] provides the missing ingredient: for every path, a bound on the number of recursive inputs containing a subpath with large relevance, allowing us to establish a trade-off between the amount of fragmentation and the success probability of Sweep. Let GG be the input to JLS partitioning, and PP a fixed shortest dipath in GG. By Lemma 1, every recursive instance whose input subgraph contains vertices of PP contains a contiguous subpath of PP. Now consider the subproblem tree of PP, whose nodes are those recursive instances sorted by level, and whose edges link parent to child. Instances in the subproblem tree in which a fragment is resolved are treated as leaves: by the argument of Observation 1, resolving a shortest-path fragment reveals at least half its length without overestimating, so in either case we stop tracking its further subdivisions in the analysis. The following lemma ² of Ashvinkumar et al. [2] bounds the expected number of nodes in the subproblem tree where the associated fragment of PP has large relevance:

Lemma 2 (Adapted from Lemma 4.5 and Observation 4.6 in [2]). Fix a shortest path PP in the input to JLS partitioning, and a threshold x>0x > 0. Let XX be the count of nodes in the subproblem tree of PP whose associated fragment P′=P[V(H)]P' = P[V(H)] satisfies ∣RH(P′)∣≥x|R_H(P')| \ge x, where HH is the corresponding recursive input. Then:

E[X]≤n1+O(1/log⁡log⁡n)x.\mathbb{E}[X] \le\sqrt{\frac{n^{1+O(1/\log\log n)}}{x}}.

Moreover, with probability at least 1−O(n−10)1-O(n^{-10}), every node in the subproblem tree of PP has O(log⁡2n)O(\log^2 n) children.

Taken together, these bounds control the expected fragmentation of a diametral path, stopping the analysis of each subproblem when it’s fragment is resolved or when its relevance becomes sufficiently small. We show that the resulting fragments collectively yield a constant probability of success of detecting a distance at least D/n1/3+o(1)D/n^{1/3+o(1)}, either through a sampled bridge or Sweep, achieving the desired sub-n1/2n^{1/2} approximation factor.

A Polynomial Lower Bound for Reachability Diameter

We refer to the technical overview in § 2.2 for the 3-uniform Hyperclique hypothesis and the formulation of Hyperclique using variables X1,…,XKX_1,\ldots,X_K and constraints C\mathcal{C}.

Main ideas and graph construction framework

Encoding candidate assignments in the graph. We now explain how to encode the candidate assignments for X1,…,XKX_1,\ldots,X_K in our layered graph. At a high level, each trajectory in the graph encodes an assignment to the variables X1,…,XKX_1,\ldots,X_K.

We begin by outlining the graph construction. Consider a vertex represented by the coordinates (τ,x1,x2,…)(\tau,x_1,x_2,\ldots), where τ\tau denotes its layer and x=(x1,x2,…)\mathbf{x}=(x_1,x_2,\ldots) gives its coordinates within that layer. Now, consider two vertices (τ1,x)(\tau_1,\mathbf{x}) and (τ2,y)(\tau_2,\mathbf{y}) with τ1<τ2\tau_1 < \tau_2. If (yi−xi)/(τ2−τ1)(y_i-x_i)/(\tau_2-\tau_1) is an integer for every ii, we can obtain the second endpoint from the first by advancing one layer at a time and changing the ii-th coordinate by exactly (yi−xi)/(τ2−τ1)(y_i-x_i)/(\tau_2-\tau_1) at each step. Thus, the two vertices determine a constant direction across these layers. We call such a pair of vertices a valid pair.3 For a valid pair ((τ1,x),(τ2,y))((\tau_1,\mathbf{x}),(\tau_2,\mathbf{y})), the direction is a=(y−x)/(τ2−τ1)\mathbf{a}=(\mathbf{y}-\mathbf{x})/(\tau_2-\tau_1). Let b=x−τ1a=y−τ2a\mathbf{b}=\mathbf{x}-\tau_1\mathbf{a}=\mathbf{y}-\tau_2\mathbf{a} denote the intercept of the pair. By fixing a\mathbf{a} and b\mathbf{b}, each valid pair determines dipaths starting from (0,b)(0,\mathbf{b}) that follows a constant direction. We call such dipaths follow the same trajectory.

Thus, the amount of information a trajectory can encode is determined by the possible choices of b\mathbf{b} and a\mathbf{a}. Hence, all the information carried by a trajectory is contained in b\mathbf{b} and a\mathbf{a}, so encoding an assignment in a trajectory amounts to encoding it in these two vectors. In the meanwhile, the number of possible choices of b\mathbf{b} and a\mathbf{a} determines how many distinct trajectories we can use. By assigning different blocks to different variables, we can distribute the values of X1,…,XKX_1,\ldots,X_K across the starting coordinates b\mathbf{b} and the direction components a\mathbf{a}. Thus, we ensure that every candidate assignment to X1,…,XrX_1,\ldots,X_r is represented by a trajectory whose vertices all belong to the graph.

Compressing a failing trajectory. Recall that our goal is to construct a digraph whose reachability diameter is large if and only if there exists an assignment to X1,…,XKX_1,\ldots,X_K satisfying every constraint in CC.

Consider any valid pair in the digraph. The two vertices uniquely determine the intercept b\mathbf{b} and direction a\mathbf{a} of the corresponding trajectory. Starting from (0,b)(0,\mathbf{b}) and moving in direction a\mathbf{a} from one layer to the next, we obtain a unique vertex (τ,b+τa)(\tau,\mathbf{b}+\tau\mathbf{a}) in each layer τ\tau. We call these vertices as vertices on the trajectory. In our construction, we ensure that the vertices on each trajectory in any two consecutive layers are connected by a constant-length dipath from the earlier layer to the later layer. Note that any pair of vertices on the trajectory is a valid pair by definition.

If the trajectory determined by b\mathbf{b} and a\mathbf{a} encodes an assignment that violates a constraint in CC, we call it a failing trajectory. We want every pair of vertices on a failing trajectory to be connected by a short path from the earlier layer to the later layer. Thus, a failing trajectory should not force a large diameter. A simple solution is to add a shortcut from every earlier vertex to every later vertex on the trajectory, but enumerating all pairs would be too expensive.

To reduce the number of pairs we need to connect directly, we choose a collection of intervals of layers. Let L≥2L \ge2 be a power of two, and denote the total number of layers. For each length ℓ∈{1,2,4,…,L}\ell\in\{1,2,4,\ldots,L\}, we choose the intervals I=[jℓ,(j+1)ℓ]⊆[0,L]I=[j\ell,(j+1)\ell]\subseteq[0,L], where jj is a nonnegative integer. For example, when ℓ=2\ell=2, we choose [0,2],[2,4],…,[L−2,L][0,2],[2,4],\ldots,[L-2,L]. Each interval has length equal to a power of two and starts at a multiple of its length, which is called as a dyadic interval.

For a failing trajectory, we will construct a constant-length shortcut between any pair of vertices on the trajectory in each dyadic interval. We also ensure that each shortcut has the same direction as the trajectory determined by the two vertices it connects.

Fix any two vertices on the trajectory, the interval between their layers can be partitioned into at most 2log⁡L2\log L dyadic intervals. To see this, consider any interval [s,t]⊆[0,L][s,t]\subseteq[0,L]. Start with the unit intervals between ss and tt, and repeatedly merge two adjacent intervals whenever their union is a dyadic interval, until no further merges are possible. Given the construction of the dyadic intervals, at most of two intervals of each length remain. Thus, the resulting partition contains only O(log⁡L)O(\log L) dyadic intervals.

In conclusion, we only need to construct constant-length shortcuts for the 2L−12L-1 aligned dyadic intervals in [0,L][0,L] to obtain short paths between every pair of vertices on a failing trajectory.

Protecting a satisfying trajectory. Consider a trajectory determined by the intercept b\mathbf{b} and direction a\mathbf{a}. Suppose its encoded assignment satisfies every constraint in CC, and such trajectory is a satisfying trajectory. We want the distance from its vertex in layer 00 to its vertex in layer LL to remain large such that we force the existence of a large reachability diameter in this case.

However, our current construction cannot yet guarantee that the distance between two vertices remains large. A valid pair determines a fixed intercept and direction, but a dipath between them need not keep that direction throughout. Since different trajectories may share vertices, a dipath may change direction along the way and still reach the prescribed final vertex. If a segment of the dipath connects vertices on a failing trajectory, that segment may use the shortcuts constructed above. Thus, even though the original pair determines a satisfying trajectory, a dipath between the two vertices may still use shortcuts for failing assignments.

To prevent such a dipath, we need to ensure that a dipath connecting a valid pair on the corresponding trajectory cannot switch to a different direction.

Recall that moving in direction a\mathbf{a} from one layer to the next changes x\mathbf{x} by a\mathbf{a}. We add a coordinate zz to each vertex, called the energy coordinate. For every move in direction a\mathbf{a} between consecutive layers, we require zz to increase by ∥a∥2\lVert\mathbf{a}\rVert^2. Just as b\mathbf{b} gives the coordinates x\mathbf{x} in layer 0, let ee denote the value of zz in layer 0. Starting from (0,b,e)(0,\mathbf{b},e) and applying these changes from one layer to the next, we obtain the vertex on the trajectory in layer τ\tau with coordinates

(τ,x(τ),z(τ))=(τ,b+τa,e+τ∥a∥2).(1)(\tau,\mathbf{x}(\tau),z(\tau))=(\tau,\mathbf{b}+\tau\mathbf{a},e+\tau\lVert\mathbf{a}\rVert^2). \tag*{(1)}

Thus, with the energy coordinate included, b\mathbf{b}, ee, and a\mathbf{a} determine a trajectory.

Recall that a constant-length shortcut between any two vertices on this trajectory also follows direction a\mathbf{a}. If a constant-length shortcut is added between two vertices on this trajectory in layers τ1<τ2\tau_1 < \tau_2, we require the total increase in zz along the shortcut to be (τ2−τ1)∥a∥2(\tau_2-\tau_1)\lVert\mathbf{a}\rVert^2. Thus, the energy coordinate changes from e+τ1∥a∥2e+\tau_1\lVert\mathbf{a}\rVert^2 to e+τ2∥a∥2e+\tau_2\lVert\mathbf{a}\rVert^2, exactly as it would when moving in direction a\mathbf{a} from one layer to the next.

We next explain why the energy coordinate prevents a dipath between two vertices on a trajectory from switching directions.

The argument adapts the convexity proof in [12 Section 2.1, Lemma 2]. Fix two vertices on the trajectory determined by b\mathbf{b}, ee, and a\mathbf{a}, and consider a dipath from the earlier vertex to the later vertex. Suppose for contradiction that a dipath between does not keep the same direction of a\mathbf{a} throughout. Thus, we can divide the dipath into segments, each of which follows a fixed direction throughout. A segment may contain any number of moves between consecutive layers or shortcuts across dyadic intervals, provided that they all have the same direction. Let a1,…,ar\mathbf{a}_1,\ldots,\mathbf{a}_r be the directions of these segments. For segment jj, let ℓj>0\ell_j>0 be the difference between the layer indices of its first and last vertices.

Thus, segment jj changes x\mathbf{x} by ℓjaj\ell_j\mathbf{a}_j and zz by ℓj∥aj∥2\ell_j\lVert\mathbf{a}_j\rVert^2. Let T=∑jℓjT=\sum_j\ell_j be the difference between the layers of the two fixed vertices. Since both vertices lie on the trajectory with direction a\mathbf{a}, the total changes in x\mathbf{x} and zz must also be TaT\mathbf{a} and T∥a∥2T\lVert\mathbf{a}\rVert^2, respectively. Hence,

∑jℓjaj=Ta,∑jℓj∥aj∥2=T∥a∥2.\sum_j \ell_j\mathbf{a}_j=T\mathbf{a},\qquad\sum_j \ell_j\lVert\mathbf{a}_j\rVert^2=T\lVert\mathbf{a}\rVert^2.

Consequently,

∑jℓj∥aj−a∥2=T∥a∥2−2T∥a∥2+T∥a∥2=0.(2)\sum_j \ell_j\lVert\mathbf{a}_j-\mathbf{a}\rVert^2=T\lVert\mathbf{a}\rVert^2-2T\lVert\mathbf{a}\rVert^2+T\lVert\mathbf{a}\rVert^2=0. \tag*{(2)}

Every term in the sum is nonnegative, and every ℓj\ell_j is positive. Hence, aj=a\mathbf{a}_j=\mathbf{a} for every segment jj. In conclusion, every dipath connecting the a valid pair must always follow the direction of the trajectory determined by that pair.

Now, consider a valid pair with one vertex in layer 0 and the other in layer LL, and suppose the trajectory determined by this pair is a satisfying trajectory. No dipath between the two vertices can use a shortcut belonging to a different trajectory, since using such a shortcut would require changing direction.

Recall that after adding the energy coordinate, we need the intercept b\mathbf{b}, the direction a\mathbf{a}, and ee to specify a trajectory. We also use ee to encode some part of the variables from X1,…,XKX_1,\ldots,X_K, just as how we use the b\mathbf{b} and a\mathbf{a}. Otherwise, the energy coordinate would enlarge the graph without increasing the number of assignments we can encode, weakening the reduction.

Choosing the number of coordinates. Recall that we encode the values of X1,…,XKX_1,\ldots,X_K in the intercept b\mathbf{b}, the direction a\mathbf{a}, and ee. We have not yet specified how many coordinates x\mathbf{x} has. Since b\mathbf{b} and a\mathbf{a} each have one component for every coordinate of x\mathbf{x}, adding one coordinate gives us two more components in which to encode variable values.

However, more coordinates also increase the size of the graph and the cost of constructing it. Thus, we need to balance the number of assignments we can encode against the size of the graph and the time needed to construct it. We choose three coordinates, x=(x1,x2,x3)\mathbf{x}=(x_1,x_2,x_3), together with the energy coordinate zz, so that b\mathbf{b} and a\mathbf{a} each have three components. Our analysis shows that using three coordinates gives the strongest lower bound on the approximation ratio for this construction. We justify this choice in Section 3.6, after deriving these size bounds.

We summarize the construction described so far in Algorithm 2. In the next subsection, we describe how to add edges to connect vertices in consecutive layers and how to implement the constant-length shortcuts.

Algorithm 2 Graph Construction Framework

Input: Constraints C\mathcal{C} on X1,…,XKX_1,\ldots,X_K and L≥2L\geq2

  1. Choose bounded ranges for x=(x1,x2,x3)\mathbf{x}=(x_1,x_2,x_3) and the direction a\mathbf{a}.

  2. Create vertices (τ,x,z)(\tau,\mathbf{x},z) in layers τ=0,…,L\tau=0,\ldots,L, with coordinates restricted to the chosen ranges.

  3. Encode each assignment to X1,…,XKX_1,\ldots,X_K in b\mathbf{b}, a\mathbf{a}, and ee.

  4. Connect vertices on the same trajectory in consecutive layers: (τ,x,z)⟶(τ+1,x+a,z+∥a∥2)(\tau,\mathbf{x},z)\longrightarrow(\tau+1,\mathbf{x}+\mathbf{a},z+\lVert\mathbf{a}\rVert^2).

  5. for each dyadic interval I=[τ,τ+ℓ]I=[\tau,\tau+\ell] with ℓ≥2\ell\geq2 do

  6. For a failing trajectory, add a shortcut between vertices in layers τ\tau and τ+ℓ\tau+\ell: (τ,x,z)⟶(τ+ℓ,x+ℓa,z+ℓ∥a∥2)(\tau,\mathbf{x},z)\longrightarrow(\tau+\ell,\mathbf{x}+\ell\mathbf{a},z+\ell\lVert\mathbf{a}\rVert^2).

  7. end for

Connecting consecutive layers and adding shortcuts

Recall that we need to connect vertices on the same trajectory in consecutive layers, and to add constant-length shortcuts across dyadic intervals for failing trajectories. To realize this, We first choose the direction components one at a time to connect consecutive layers. We then use the same construction for shortcuts, adding checks to ensure that a shortcut is available only when the encoded assignment violates a constraint in C\mathcal{C}.

First, we will specify the coordinate ranges.

Choosing the coordinate ranges. Let qq be the number of choices for each direction component, so that 0≤ai<q0\leq a_i<q for each i∈{1,2,3}i\in\{1,2,3\}. Recall that advancing one layer increases xix_i by aia_i and zz by ∥a∥2\lVert\mathbf{a}\rVert^2. Over LL layers, each xix_i increases by less than LqLq, and zz increases by less than 3Lq23Lq^2. Thus, if we choose 0≤bi<Lq0\leq b_i<Lq and 0≤e<Lq20\leq e<Lq^2, every vertex on the trajectory from layer 0 to layer LL satisfies 0≤xi<2Lq0\leq x_i<2Lq and 0≤z<4Lq20\leq z<4Lq^2.

In each layer τ=0,…,L\tau=0,\ldots,L, we create all vertices (τ,x1,x2,x3,z)(\tau,x_1,x_2,x_3,z) with integer coordinates satisfying 0≤xi<2Lq0\leq x_i<2Lq for i=1,2,3i=1,2,3 and 0≤z<4Lq0\leq z<4Lq. We call them base vertices to distinguish them from the auxiliary vertices introduced later. For convenience, write B=Lq2B = Lq^{2} and let UU denote the set of allowed coordinates (x,z)(x,z): U=[2Lq]3×[4B]U = [2Lq]^{3} \times[4B]. In particular, ∣U∣=32L4q5|U| = 32L^{4}q^{5}.

Connecting consecutive layers. Consider a base vertex in layer τ\tau. There are q3q^{3} choices of a\mathbf{a}, so adding a separate edge for every direction would be too expensive.

Instead, we introduce two auxiliary layers between layers τ\tau and τ+1\tau+1, each containing one vertex for every (x,z)∈U(x,z) \in U. We add edges from layer τ\tau to the first auxiliary layer, then to the second auxiliary layer, and finally to layer τ+1\tau+1. The ii-th edge of each resulting three-edge dipath chooses aia_i and updates only xix_i and zz. More specifically, the ii-th edge updates xix_i to xi+aix_i+a_i and zz to z+ai2z+a_i^{2}.

A three-edge dipath combines one choice of a1a_1, one of a2a_2, and one of a3a_3. These combinations represent all q3q^{3} directions without requiring us to enumerate them explicitly when constructing the edges. Thus, each vertex needs only qq choices for its outgoing edges. Moreover, the three-edge dipath gives the required total changes in x\mathbf{x} and zz. Conversely, consider two base vertices on the same trajectory in consecutive layers, with 0≤ai<q0 \leq a_i < q. Choosing their direction components in the three stages gives a dipath between them. Every intermediate coordinate lies between its values at the two base vertices, so all intermediate vertices belong to the corresponding copies of UU.

This construction is inspired by the alternation product of Huang and Pettie [12 Section 2.2], which builds on Hesse’s construction [11].

Add constant-length shortcuts. For a dyadic interval I=[τ,τ+ℓ]I = [\tau,\tau+\ell] with ℓ≥2\ell\geq2, we add a constant-length shortcut in a similar way with changes ℓa\ell\mathbf{a} and ℓ∥a∥2\ell\|\mathbf{a}\|^{2} in x\mathbf{x} and zz. However, we want a shortcut only when the trajectory determined by the two base vertices is failing.

The difficulty is that we construct the three edges of a shortcut by choosing a1a_1, a2a_2, and a3a_3 separately. When constructing the edge that chooses aia_i, we can recover bi=xi−τaib_i = x_i-\tau a_i, and decode the variables stored in aia_i and bib_i. How can these variables collectively determine whether the complete assignment violates a constraint in CC without exhaustive enumeration?

Note that an assignment is failing if it violates at least one constraint in CC. Thus, we can test the constraints separately. For each C∈CC \in\mathcal{C}, we create a channel with its own two auxiliary layers. Our goal is to allow a complete three-edge dipath through this channel exactly when the encoded assignment violates CC. Thus, a failing assignment only needs to allow a dipath through one of these channels.

To violate CC, all three variables involved in CC must equal their corresponding forbidden values. When constructing an edge that chooses aia_i, we check every variable of CC stored in aia_i or bib_i, and add the edge only if all their decoded values match the forbidden values specified by CC. If neither aia_i nor bib_i stores a variable of CC, we keep the edge without imposing any condition from CC. Since each channel has its own auxiliary vertices, a dipath through the channel must pass the checks for the same constraint on all three edges. These checks ensure that every variable of CC stored in aa or bb has its forbidden value.

To ensure that a complete dipath is available only when CC is violated, we must also check any variables of CC stored in ee. We explain how to perform this remaining check next.

Unlike bib_i, the value of ee depends on all three direction components since e=z−τ∥a∥2e = z-\tau\|\mathbf{a}\|^{2}. We cannot recover ee from the choice of a single component of the direction. Instead, we guess the energy coordinate of the base vertex in layer τ+ℓ\tau+\ell. Together with the energy coordinate of the base vertex in layer τ\tau, this guess determines ee. On the edge leaving the base vertex in layer τ\tau, we use the resulting value of ee to check the variables of CC stored in ee. On the edge entering the base vertex in layer τ+ℓ\tau+\ell, we require the energy coordinate reached by that edge to equal the guess.

To see why this works, write τ=jℓ\tau= j\ell, where jj is a non-negative integer. Let z0z_0 and z1z_1 denote the energy coordinates of the two base vertices in layers τ\tau and τ+ℓ\tau+\ell, respectively. A complete three-edge dipath satisfies z1−z0=ℓ∥a∥2z_1-z_0=\ell\lVert a\rVert^2, so

e=z0−τ∥a∥2=(j+1)z0−jz1.(3)e=z_0-\tau\lVert a\rVert^2=(j+1)z_0-jz_1. \tag*{(3)}

We now explain how to modify the graph construction accordingly. For each C∈CC\in\mathcal{C}, create a separate channel for every integer guess 0≤z<4B0\le z<4B of z1z_1. On the edge leaving layer τ\tau, use (j+1)z0−jz(j+1)z_0-jz as the value of ee and require all variables of CC stored there to equal their forbidden values. On the edge entering layer τ+ℓ\tau+\ell, we require the energy coordinate z1z_1 of the base vertex reached by the shortcut to equal the guessed value zz. Since channels for different guesses have separate auxiliary vertices, the guess verified at layer τ+ℓ\tau+\ell must be the same one used to compute ee on the edge leaving layer τ\tau. Thus, a complete three-edge dipath through the channel guarantees that the variables of CC stored in ee were checked using the correct value of ee.

Now, consider two base vertices on the same trajectory in layers τ\tau and τ+ℓ\tau+\ell, with 0≤ai<q0\le a_i<q. If the trajectory is failing, choose a constraint CC violated by its encoded assignment. The channel corresponding to CC and the energy guess z=z1z=z_1 then passes all checks and provides a three-edge shortcut between the two vertices. Conversely, a complete dipath through the channel corresponding to CC and zz guarantees that z1=zz_1=z and that the encoded assignment violates CC. Thus, these channels provide shortcuts precisely for failing trajectories. This construction uses 4B∣C∣4B|\mathcal{C}| channels per dyadic interval of length at least two. Algorithm 3 summarizes the construction.

Specifying the encoding.

We now specify the digit allocation and how choose ranges large enough to represent every candidate assignment. Each variable in X1,…,XKX_1,\ldots,X_K takes a value in [N][N], so one base-NN digit suffices to store it. For each trajectory, we write each component of bb and aa, as well as ee, in base NN and use the resulting digits to encode a unique assignment to X1,…,XKX_1,\ldots,X_K.

We now choose qq and LL and specify how many variables to encode in each of these components. Since LL must be a power of two for the dyadic intervals, let QQ be the smallest power of two at least 2N2N, so that 2N≤Q<4N2N\le Q<4N. Choose q=Qκq=Q^\kappa and L=QλL=Q^\lambda, where κ\kappa and λ\lambda are positive integer constants to be fixed in Section 3.6. Then the bounds 2Lq2Lq for each xix_i and 4Lq24Lq^2 for zz are polynomial in NN.

Since Nκ≤qN^\kappa\le q, each direction component aia_i can store at least κ\kappa variables from X1,…,XKX_1,\ldots,X_K. Similarly, each intercept component bib_i can store κ+λ\kappa+\lambda variable values because Lq=Qκ+λLq=Q^{\kappa+\lambda}. The energy coordinate ee in layer 0 can store s=2κ+λs=2\kappa+\lambda variable values since B=QsB=Q^s.

Thus, to store all the variables in X1,…,XKX_1,\ldots,X_K, we let 3κ+3(κ+λ)+s=4s=K3\kappa+3(\kappa+\lambda)+s=4s=K. Assign X1,…,XKX_1,\ldots,X_K in order to the base-NN digits of a1,a2,a3,b1,b2,b3,ea_1,a_2,a_3,b_1,b_2,b_3,e, using κ\kappa digits in each aia_i, κ+λ\kappa+\lambda digits in each bib_i, and ss digits in ee. Within each component, assign variables starting with the least significant digit. This order is arbitrary since we only need to fix a one-to-one correspondence between the variables and these digit positions.

Given any assignment to X1,…,XKX_1,\ldots,X_K, form each aia_i, bib_i, and ee by placing the values of its assigned variables in these fixed digit positions. The resulting integers satisfy 0≤ai<Nκ≤q0\le a_i<N^\kappa\le q, 0≤bi<Nκ+λ≤Lq0\le b_i<N^{\kappa+\lambda}\le Lq, and 0≤e<Ns≤B0\le e<N^s\le B. Hence, every candidate assignment is represented by a trajectory in the graph.

In the next subsection, we change how variables are encoded in ee by using the Chinese remainder theorem so that checking CC requires guessing only the energy information needed to read the variables of CC stored in ee. This will further decrease the size of the constructed graph and give us a stronger reduction.

Algorithm 3 Detailed graph construction

Input: UU, LL, qq, constraints C\mathcal{C}, and the digit decoder

  1. Create all base vertices (τ,x,z)(\tau, x, z) with τ=0,…,L\tau= 0, \ldots, L and (x,z)∈U(x, z) \in U. ▷ Connect vertices on the same trajectory in consecutive layers.

  2. for each unit interval I=[τ,τ+1]I = [\tau, \tau+ 1] do

  3. Create two copies of UU as auxiliary layers between layers τ\tau and τ+1\tau+ 1.

  4. For each a1∈[q]a_1 \in[q], (x,z)∈U(x, z) \in U, add (τ,x,z)→(x1+a1,x2,x3,z+a12)(\tau, x, z) \to(x_1 + a_1, x_2, x_3, z + a_1^2).

  5. For each a2∈[q]a_2 \in[q], (x,z)∈U(x, z) \in U, add (x,z)→(x1,x2+a2,x3,z+a22)(x, z) \to(x_1, x_2 + a_2, x_3, z + a_2^2).

  6. For each a3∈[q]a_3 \in[q], (x,z)∈U(x, z) \in U, add (x,z)→(τ+1,x1,x2,x3+a3,z+a32)(x, z) \to(\tau+ 1, x_1, x_2, x_3 + a_3, z + a_3^2).

  7. end for ▷ Add constant-length shortcuts across dyadic intervals for failing trajectories.

  8. for each dyadic interval I=[τ,τ+ℓ]I = [\tau, \tau+ \ell] with τ=jℓ\tau= j\ell and ℓ≥2\ell\ge2 do

  9. &nbsp;&nbsp;&nbsp;&nbsp;for each C∈CC \in\mathcal{C} and integer guess 0≤z<4B0 \le z < 4B do

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Create two copies of UU as auxiliary layers for each CC and zz.

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for each i=1,2,3i = 1, 2, 3, ai∈[q]a_i \in[q], and (x,z′)∈U(x, z') \in U do

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if i=1i = 1 then

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If every variable of CC encoded in bib_i, aia_i, or ee equals its forbidden value, add (τ,x,z′)→(x1+ℓa1,x2,x3,z′+ℓa12)(\tau, x, z') \to(x_1 + \ell a_1, x_2, x_3, z' + \ell a_1^2).

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if i=2i = 2 then

  15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If every variable of CC encoded in bib_i or aia_i equals its forbidden value, add (x,z′)→(x1,x2+ℓa2,x3,z′+ℓa22)(x, z') \to(x_1, x_2 + \ell a_2, x_3, z' + \ell a_2^2).

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if i=3i = 3 then

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If every variable of CC encoded in bib_i or aia_i equals its forbidden value and z′+ℓa32=zz' + \ell a_3^2 = z, add (x,z′)→(τ+ℓ,x1,x2,x3+ℓa3,z)(x, z') \to(\tau+ \ell, x_1, x_2, x_3 + \ell a_3, z).

  18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end for

  20. &nbsp;&nbsp;&nbsp;&nbsp;end for

  21. end for

Compressing the energy encoding with the Chinese remainder theorem

Recall that, for each constraint CC and dyadic interval [τ,τ+ℓ][\tau, \tau+ \ell] with ℓ≥2\ell\ge2, the previous construction creates a separate channel for every possible energy coordinate of the base vertex in layer τ+ℓ\tau+ \ell. This requires 4B4B guesses and two auxiliary layers for each guess. However, CC involves only three variables, and we only need the information that determines the values of those stored in ee. Intuitively, if we could divide the energy coordinate encoding into parts that can be read independently, then checking CC would require only the parts storing its variables. We could then guess only the relevant energy information, reducing the number of auxiliary layers and the cost of constructing the graph. Here, Chinese remainder theorem comes to rescue.

Encoding variables by remainders. For distinct primes p1,…,psp_1, \ldots, p_s, the Chinese remainder theorem states that any prescribed remainders modulo these primes determine a unique integer between 00 and ∏r=1spr−1\prod_{r=1}^{s} p_r - 1. Thus, we can encode an assignment to X1,…,XrX_1, \ldots, X_r by prescribing remainders that represent its variable values. These remainders then uniquely determine an energy coordinate ee in the range ∏r=1spr−1\prod_{r=1}^{s} p_r - 1.

Recall that the energy coordinate ee in layer 00 stores ss of the variables X1,…,XKX_1,\ldots,X_K. To change how these variables are encoded, we need the remainders to represent every possible assignment to these ss variables. Under these conditions, changing the encoding preserves our ability to represent every candidate assignment.

More specifically, we use one remainder to store one variable. We choose ss distinct primes p1,…,ps∈[N,2N]p_1,\ldots,p_s \in[N,2N] and use the remainders e mod p1,…,e mod pse \bmod p_1,\ldots,e \bmod p_s to encode the variables stored in ee, in the same order as in the previous encoding. Since each prime satisfies pr≥Np_r \ge N, so its possible remainders include all the variable values in [N][N].

Since ss is fixed, the prime number theorem guarantees that [N,2N][N,2N] contains at least ss distinct primes for all sufficiently large NN. Recall that Q≥2NQ \ge2N and B=QsB = Q^s, so these primes satisfy

Ns≤∏r=1spr≤(2N)s≤Qs=B.N^s \le\prod_{r=1}^{s} p_r \le(2N)^s \le Q^s = B.

Thus, by the Chinese remainder theorem, for any assignment to the ss variables stored in ee, there exists an integer 0≤e<∏r=1spr≤B0 \le e < \prod_{r=1}^{s} p_r \le B such that each remainder e mod pre \bmod p_r equals the prescribed value of the variable encoded by that remainder.

We keep the encodings of aa and bb unchanged, so the chosen components satisfy 0≤ai<q0 \le a_i < q and 0≤bi<Lq0 \le b_i < Lq. For every layer 0≤τ≤L0 \le\tau\le L, the corresponding coordinates therefore satisfy

0≤bi+τai<2Lq,0≤e+τ∥a∥2<B+3Lq2=4B.0 \le b_i+\tau a_i < 2Lq,\qquad0 \le e+\tau\lVert a\rVert^2 < B+3Lq^2 = 4B.

Thus, every base vertex on this trajectory from layer 00 to layer LL belongs to the graph, which means every candidate assignment to X1,…,XrX_1,\ldots,X_r has such a trajectory representation.

Once the primes are fixed, we read the value of the variable assigned with respect to prp_r as (e mod pr) mod N(e \bmod p_r) \bmod N. The final reduction modulo NN ensures that the value belongs to [N][N].

Checking constraints using energy remainders. For a constraint CC, let MCM_C be the product of all primes prp_r for which the remainder e mod pre \bmod p_r encodes a variable of CC. If no variable of CC is stored in ee, let MC=1M_C=1.

Now, consider a dyadic interval I=[τ,τ+ℓ]I=[\tau,\tau+\ell] with ℓ≥2\ell\ge2 and τ=jℓ\tau=j\ell. To construct a constant-length shortcut, instead of guessing the entire energy coordinate z1z_1 in layer τ=jℓ\tau=j\ell, we guess only its remainder r1=z1 mod MCr_1=z_1 \bmod M_C. To see this, suppose that the energy coordinate in layer τ=jℓ\tau=j\ell is z0z_0. Then, we have

e≡(j+1)z0−jz1≡(j+1)z0−jr1(modMC).(4)e \equiv(j+1)z_0-jz_1 \equiv(j+1)z_0-jr_1 \pmod{M_C}. \tag*{(4)}

Thus, by guessing r1r_1, it is enough to check the variables of CC stored in ee.

We now modify the construction of the constant-length shortcuts accordingly. For each CC and each guessed remainder r1∈[MC]r_1 \in[M_C], create two copies of UU as auxiliary layers between layers τ\tau and τ+ℓ\tau+\ell. As before, a dipath through these auxiliary layers chooses a1,a2,a3a_1,a_2,a_3 on its three edges, respectively. The edge choosing aia_i changes xix_i to xi+ℓaix_i+\ell a_i and zz to z+ℓai2z+\ell a_i^2. When choosing aia_i, we check that every variable of CC stored in aia_i or bi=xi−τaib_i=x_i-\tau a_i equals its forbidden value.

On the edge from layer τ\tau to the first auxiliary layer, use ((j+1)z0−jr1) mod MC((j+1)z_0-jr_1) \bmod M_C as the to read the variables of CC stored in ee. Add the edge whenever no variable of CC stored in a1a_1, b1b_1, and ee has a value different from its forbidden value. Add an edge from the first auxiliary layer to the second auxiliary layer if no variable of CC stored in a2a_2 or b2b_2 differs from its forbidden value. Add an edge from the second auxiliary layer to a base vertex in layer τ+ℓ\tau+\ell if no variable of CC stored in a3a_3 or b3b_3 differs from its forbidden value and the energy coordinate z1z_1 of that base vertex satisfies z1 mod MC=r1z_1 \bmod M_C=r_1.

New construction analysis. Fix a constraint C∈CC \in\mathcal{C}, we now only need MCM_C pairs of auxiliary layers instead of 4B4B. Since CC involves only three variables, MCM_C is a product of at most three primes. Hence, MC≤(2N)3M_C \le(2N)^3. Since ∣C∣≤(K3)N3|\mathcal{C}| \le\binom{K}{3}N^3, we have ∑C∈CMC=OK(N6)\sum_{C\in\mathcal{C}} M_C = O_K(N^6).

Algorithm 4 summarizes the changes to the shortcut construction in Algorithm 3. Together with the edges connecting consecutive layers from Algorithm 3, these shortcuts give the final graph.

Algorithm 4 Shortcut construction using energy remainders

  1. Choose ss distinct primes p1,…,ps∈[N,2N]p_1,\ldots,p_s \in[N,2N].

  2. Add constant-length shortcuts across dyadic intervals for failing trajectories.

  3. for each dyadic interval I=[τ,τ+ℓ]I=[\tau,\tau+\ell] with τ=jℓ\tau=j\ell and ℓ≥2\ell\ge2 do

  4. &nbsp;&nbsp;for each C∈CC \in\mathcal{C} and guessed remainder r1∈[MC]r_1 \in[M_C] do

  5. &nbsp;&nbsp;&nbsp;&nbsp;Create two copies of UU as auxiliary layers for C,r1C,r_1 between layers τ\tau and τ+ℓ\tau+\ell.

  6. &nbsp;&nbsp;&nbsp;&nbsp;for each i=1,2,3i=1,2,3, ai∈[q]a_i \in[q], and (x,z′)∈U(\mathbf{x},z') \in U do

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Let bi=xi−τaib_i=x_i-\tau a_i.

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if i=1i=1 then

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If no variable of CC encoded in bib_i, aia_i, or (((j+1)z′−jr1) mod pr)(((j+1)z'-jr_1)\bmod p_r) differs from its forbidden value, add

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(τ,x,z′)→(x1+ℓa1,x2,x3,z′+ℓa2)(\tau,\mathbf{x},z')\to(x_1+\ell a_1,x_2,x_3,z'+\ell a_2).

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if i=2i=2 then

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If no variable of CC encoded in bib_i or aia_i differs from its forbidden value, add

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(x,z′)→(x1,x2+ℓa2,x3,z′+ℓa2)(\mathbf{x},z')\to(x_1,x_2+\ell a_2,x_3,z'+\ell a_2).

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if i=3i=3 then

  15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If (z′+ℓa23) mod MC=r1(z'+\ell a_2^3)\bmod M_C=r_1 and no variable of CC encoded in bib_i or aia_i differs from its forbidden value, add

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(x,z′)→(τ+ℓ,x1,x2,x3+ℓa3,z′+ℓa23)(\mathbf{x},z')\to(\tau+\ell,x_1,x_2,x_3+\ell a_3,z'+\ell a_2^3).

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  18. &nbsp;&nbsp;&nbsp;&nbsp;end for

  19. &nbsp;&nbsp;end for

  20. end for

The diameter gap

Recall that every candidate assignment is represented by a trajectory, and that we add shortcuts only for failing trajectories. We now show that these properties give the required diameter gap. If a satisfying assignment exists, we will find two base vertices at distance 3L3L. If every assignment violates a constraint, we will first bound the distance between vertices on the same trajectory, and then extend the bound to any two vertices connected by a dipath.

We begin by applying the argument from § 3.1 to the graph constructed in § 3.2 and § 3.4.

Lemma 3 (Dipaths between vertices on the same trajectory). Let uu and vv be a valid pair on the trajectory with direction a\mathbf{a}, with uu in an earlier layer than vv. Every dipath from uu to vv always follows direction a\mathbf{a} when moving through consecutive layers and or using a shortcut.

Proof. Consider any dipath from uu to vv. Between successive base vertices, it uses either a three-edge dipath connecting consecutive layers or a three-edge shortcut across a dyadic interval.

For the jj-th pair of successive base vertices, let aja_j be the direction chosen by the three edges between them, and let ℓj\ell_j be the difference between their layers. The three edges together increase xx by ℓjaj\ell_j a_j and zz by ℓj∥aj∥2\ell_j\lVert a_j\rVert^2. Thus, (2) gives aj=aa_j = a for every jj.

Lemma 4 (Diameter gap). Let DD denote the reachability diameter of the constructed digraph by Algorithm 3 and Algorithm 4. If there is an assignment to X1,…,XKX_1,\ldots,X_K satisfying every constraint in CC, then D≥3LD \ge3L. Otherwise,

D≤DNO:=30log⁡Llog⁡(4B)+6.(5)D \le\mathrm{D}_{\mathrm{NO}} := 30\log L\log(4B)+6. \tag*{(5)}

Proof. When a satisfying assignment exists. By § 3.4, the assignment is represented by a trajectory whose base vertices in every layer from $0$ to LL belong to the graph. Let uu and vv be its base vertices in layers 00 and LL. The construction connects its vertices in consecutive layers by three-edge dipaths, giving a dipath of length 3L3L from uu to $v.

By Lemma 3, every dipath from uu to vv follows the same direction, and all its base vertices lie on this satisfying trajectory. Such a dipath cannot use a shortcut since the shortcuts are only added between valid pairs on a failing trajectory. Hence, every dipath from uu to vv uses only connections between consecutive layers. Each such connection has three edges, so D≥d(u,v)=3LD \ge d(u,v) = 3L.

When there is no satisfying assignment. Suppose now that every assignment violates a constraint in CC. We first consider two base vertices on the same trajectory, with ai∈[q]a_i \in[q] for i=1,2,3i = 1,2,3.

Since every assignment violates a constraint, this trajectory is failing. Consider a dyadic interval [τ,τ+ℓ][\tau,\tau+\ell] between the layers of the two fixed base vertices. If ℓ≥2\ell\ge2, choose a constraint CC violated by the trajectory’s assignment and r1=z1 mod MCr_1 = z_1 \bmod M_C, where z1z_1 is the energy coordinate of its base vertex in layer τ+ℓ\tau+\ell. By (4), the first edge reads the correct values of the variables of CC stored in ee. All the variable checks pass, and the last edge verifies r1r_1. Hence, the two auxiliary layers for C,r1C,r_1 give a three-edge shortcut.

As explained in § 3.1, the interval between the layers of the two fixed vertices can be partitioned into at most 2log⁡L2\log L dyadic intervals. Thus, concatenating the three-edge dipaths for these intervals gives a dipath of length at most 6log⁡L6\log L.

Nevertheless, two base vertices connected by a dipath may not be a valid pair and they do not determine any trajectory. In this case, we can divide the dipath into segments of constant direction, but there may be too many segments to obtain a short dipath by replacing each segment separately. Instead, there exists a dipath using only a logarithmic number of directions. Thus, there exists a dipath following each direction for consecutive layers and the O(log⁡L)O(\log L) bound be applied to each resulting segment.

To bound the number of directions, we apply the nonnegative integer-cone bound of Eisenbrand and Shmonin [8 Theorem 1(i)], using the coordinatewise bound in the proof of [20 Theorem 5.1].

Let u=(τ0,x0,z0)u=(\tau_0,\mathbf{x}_0,z_0) and v=(τ1,x1,z1)v=(\tau_1,\mathbf{x}_1,z_1) be distinct base vertices with a dipath from uu to vv. Suppose that there is a dipath from uu to vv that can be divided into segments of distinct direction a1,…,ara_1,\ldots,a_r. Thus, we have

(τ1−τ0,x1−x0,z1−z0)=∑j=1rℓj(1,aj,∥aj∥2),ℓj∈Z>0.(\tau_1-\tau_0,\mathbf{x}_1-\mathbf{x}_0,z_1-z_0)=\sum_{j=1}^{r}\ell_j(1,a_j,\lVert a_j\rVert^2),\qquad\ell_j\in\mathbb{Z}_{>0}.

By the nonnegative integer-cone bound of Eisenbrand and Shmonin [8 Theorem 1(i)], using the coordinatewise estimate in the proof of [20 Theorem 5.1], we can choose the representation so that

r≤log⁡(τ1−τ0+1)+∑i=13log⁡(x1,i−x0,i+1)+log⁡(z1−z0+1),r \le\log(\tau_1-\tau_0+1)+\sum_{i=1}^{3}\log(x_{1,i}-x_{0,i}+1)+\log(z_1-z_0+1),

where x0,ix_{0,i} and x1,ix_{1,i} are the ii-th coordinates of x0\mathbf{x}_0 and x1\mathbf{x}_1, respectively. Since τ1−τ0≤L\tau_1-\tau_0\le L, x1,i−x0,i<2Lqx_{1,i}-x_{0,i}<2Lq, and z1−z0<4Bz_1-z_0<4B, and all these differences are integers,

r≤log⁡(L+1)+3log⁡(2Lq)+log⁡(4B)≤5log⁡(4B).(6)r\le\log(L+1)+3\log(2Lq)+\log(4B)\le5\log(4B). \tag*{(6)}

Starting at uu, advance by ℓj\ell_j layers in direction aj\mathbf{a}_j for j=1,…,rj=1,\ldots,r, in order. The total changes reach vv, and all coordinates are nondecreasing. Hence, the intermediate coordinates stay between those of uu and vv, within UU, so the construction provides the required dipath. By the preceding argument, the distance of each segment is at most 6log⁡L6\log L. Concatenating these short dipaths gives d(u,v)≤6rlog⁡L≤30log⁡Llog⁡(4B)=DNOd(u,v)\le6r\log L\le30\log L\log(4B)=D_{NO}.

Finally, if a dipath contains base vertices, the portions before its first base vertex and after its last base vertex each have at most three edges. Replacing the dipath between these base vertices by the short dipath above adds at most six edges to the bound. A dipath with no base vertex stays within one pair of auxiliary layers and has at most three edges. This proves (5).

Graph size and construction time

We now count the vertices and edges created by Algorithms 3 and 4. Recall that each base or auxiliary layer contains ∣U∣|U| vertices. There are L+1L+1 base layers and two auxiliary layers for each of the LL pairs of consecutive layers. For each of the L−1L-1 dyadic intervals of length at least two, we create two auxiliary layers for every constraint C∈CC\in\mathcal{C} and guessed remainder r1∈[MC]r_1\in[M_C]. Thus, shortcuts across each such interval require ∑C∈CMC\sum_{C\in\mathcal{C}}M_C pairs of auxiliary layers.

For each pair of auxiliary layers, we add edges from the earlier base layer to the first auxiliary layer, from the first to the second auxiliary layer, and from the second auxiliary layer to the later base layer. For each of these three connections between layers, each vertex in the earlier layer has at most qq outgoing edges, one for each choice of the corresponding direction component. Thus, each pair of auxiliary layers contributes at most 3∣U∣q3|U|q edges. Therefore,

n=(3L+1)∣U∣+2(L−1)∣U∣∑C∈CMC,(7)n=(3L+1)|U|+2(L-1)|U|\sum_{C\in\mathcal{C}}M_C, \tag*{(7)}
m≤3∣U∣q[L+(L−1)∑C∈CMC].m\le3|U|q\left[L+(L-1)\sum_{C\in\mathcal{C}}M_C\right].

To construct the graph, we first list the constraints in C\mathcal{C} in OK(N3)O_K(N^3) time and find the required primes in [N,2N][N,2N] by a sieve in O~(N)\widetilde{O}(N) time. We then create all base and auxiliary vertices and consider the choices of aj∈[q]\mathbf{a}_j\in[q] for each set of edges described above. For each choice, we compute the new coordinates and perform the variable and remainder checks from § 3.2 and § 3.4. Since κ\kappa and λ\lambda are fixed, all integers involved have OK(log⁡N)O_K(\log N) bits, so each choice takes at most polylogarithmic time. The total construction time is therefore

O~K(∣U∣qL(1+∑C∈CMC)+N3).(8)\widetilde{O}_K\left(|U|qL\left(1+\sum_{C\in\mathcal{C}}M_C\right)+N^3\right). \tag*{(8)}

Recall that Q=Θ(N)Q=\Theta(N), L=QλL=Q^\lambda, q=Qκq=Q^\kappa, and ∣U∣=32L4q5|U|=32L^4q^5. Substituting these values and ∑C∈CMC=OK(N6)\sum_{C\in\mathcal{C}} M_C=O_K(N^6) from § 3.4 gives

n=OK(N5λ+5κ+6),m=OK(N5λ+6κ+6),construction time=O~K(N5λ+6κ+6).(9)\begin{aligned} n&=O_K(N^{5\lambda+5\kappa+6}),\\ m&=O_K(N^{5\lambda+6\kappa+6}),\\ \text{construction time}&=\widetilde{O}_K(N^{5\lambda+6\kappa+6}). \tag*{(9)} \end{aligned}

These bounds explain why we changed the energy encoding in § 3.4. Guessing the entire energy coordinate would require 4B∣C∣=OK(N2κ+λ+3)4B|\mathcal{C}|=O_K(N^{2\kappa+\lambda+3}) pairs of auxiliary layers per dyadic interval of length at least two. The resulting construction-time bound would have exponent 8κ+6λ+38\kappa+6\lambda+3, exceeding K=8κ+4λK=8\kappa+4\lambda. Guessing only the required remainder reduces the number of pairs to OK(N6)O_K(N^6), whose exponent does not grow with the number of variables stored in ee.

Choosing the parameters and obtaining the exponent

We now choose κ\kappa and λ\lambda so that the reduction satisfies two requirements. First, constructing the graph and running a O~(n+m)\widetilde{O}(n+m)-time approximation algorithm must take O(NK−η)O(N^{K-\eta}) time for some constant η>0\eta>0. Second, the approximation guarantee must distinguish the case where a satisfying assignment exists from the case where every assignment violates a constraint.

Recall that the construction encodes K=8κ+4λK=8\kappa+4\lambda variables. By (9), constructing the graph and running the approximation algorithm together take O~K(N5λ+6κ+6)\widetilde{O}_K(N^{5\lambda+6\kappa+6}) time. Thus, the first requirement holds whenever 5λ+6κ+6<K5\lambda+6\kappa+6<K, or equivalently, λ<2κ−6\lambda<2\kappa-6.

For the second requirement, consider an nβn^\beta-approximation for a constant β>0\beta>0. By Lemma 4, if a satisfying assignment exists, the estimate is at least 3L/nβ3L/n^\beta; otherwise, it is at most DNOD_{\mathrm{NO}}. We therefore need 3L/nβ>DNO3L/n^\beta>D_{\mathrm{NO}}. Since DNO=OK((log⁡N)2)D_{\mathrm{NO}}=O_K((\log N)^2), L=ΘK(Nλ)L=\Theta_K(N^\lambda), and n=OK(N5λ+5κ+6)n=O_K(N^{5\lambda+5\kappa+6}), it suffices to choose

β<λ5λ+5κ+6.(10)\beta<\frac{\lambda}{5\lambda+5\kappa+6}. \tag*{(10)}

For fixed κ\kappa, this ratio increases with λ\lambda. We therefore take λ=2κ−7\lambda=2\kappa-7, the largest integer satisfying λ<2κ−6\lambda<2\kappa-6, and choose κ≥4\kappa\geq4 so that λ\lambda is positive. Then K=16κ−28K=16\kappa-28, and (9) becomes

n=OK(N15κ−29),m=OK(N16κ−29)=OK(NK−1),construction time=O~K(NK−1).(11)\begin{aligned} n&=O_K(N^{15\kappa-29}),\\ m&=O_K(N^{16\kappa-29})=O_K(N^{K-1}),\\ \text{construction time}&=\widetilde{O}_K(N^{K-1}). \tag*{(11)} \end{aligned}

At the same time, L=ΘK(N2κ−7)L=\Theta_K(N^{2\kappa-7}). For this choice of λ\lambda, the right-hand side of (10) satisfies

2κ−715κ−29=215−4715(15κ−29)⟶215as κ→∞.(12)\frac{2\kappa-7}{15\kappa-29} =\frac{2}{15}-\frac{47}{15(15\kappa-29)} \longrightarrow\frac{2}{15} \quad\text{as }\kappa\to\infty. \tag*{(12)}

Thus, for every fixed ε∈(0,2/15)\varepsilon\in(0,2/15), we can choose κ\kappa large enough that β=2/15−ε\beta=2/15-\varepsilon satisfies both requirements. This gives the exponent in Theorem 2.

Optimizing the number of coordinates. We can now justify the choice of three coordinates for x\mathbf{x} in § 3.1. Suppose instead that x\mathbf{x} has dd coordinates for a fixed integer d≥2d\geq2. Both a connection between consecutive layers and a shortcut would use d−1d-1 auxiliary layers, with the dd edges choosing a1,…,ada_1,\ldots,a_d separately. Each aia_i would store κ\kappa variables, each bib_i would store κ+λ\kappa+\lambda variables, and ee would still store 2κ+λ2\kappa+\lambda variables. Thus, a trajectory would encode K=(d+1)(2κ+λ)K=(d+1)(2\kappa+\lambda) variables. Each xix_i would still range over [2Lq][2Lq]. Since the energy increase across LL layers is less than dLq2dLq^2, we would let zz range over [(d+1)B][(d+1)B]. Each base or auxiliary layer would then contain Od(Ld+1qd+2)O_d(L^{d+1}q^{d+2}) vertices. The same counting argument therefore gives a vertex bound of O~K(N(d+2)(κ+λ)+6)\widetilde{O}_K(N^{(d+2)(\kappa+\lambda)+6}) and a construction-time bound of O~K(N(d+3)κ+(d+2)λ+6)\widetilde{O}_K(N^{(d+3)\kappa+(d+2)\lambda+6}).

To keep the construction time polynomially smaller than NKN^K, we would need λ<(d−1)κ−6\lambda< (d-1)\kappa-6. For fixed dd, the same diameter analysis gives a lower bound of dLdL when a satisfying assignment exists and an upper bound of OK((log⁡N)2)O_K((\log N)^2) otherwise. Taking λ=(d−1)κ−7\lambda=(d-1)\kappa-7 and letting κ\kappa grow therefore gives the limiting approximation exponent (d−1)/(d(d+2))(d-1)/(d(d+2)). For every integer d≥2d\ge2, this is at most 2/152/15, with equality only at d=3d=3: the inequality is equivalent to (2d−5)(d−3)≥0(2d-5)(d-3)\ge0, which holds for d=2d=2 and for all d≥3d\ge3. Thus, three coordinates give the largest exponent for this construction under the size bounds above.

Upper Bound

Algorithm

Running time. Each call Sweep⁡(H)\operatorname{Sweep}(H) takes O(V(H)+E(H))O(V(H)+E(H)) time. Recursive inputs at each of O(log⁡n)O(\log n) levels are vertex-disjoint, so the total running time of Sweep⁡\operatorname{Sweep} is O((m+n)log⁡n)O((m+n)\log n). Together with Proposition 4.1 of [2], this implies that, for sufficiently large constants c1,c2c_1,c_2, an uncapped trial including the subroutine Sweep⁡\operatorname{Sweep} finishes within c1(m+n)log⁡c2(n)c_1(m+n)\log^{c_2}(n) steps with probability 1−O(n−10)1-O(n^{-10}). The worst case running time is O~(m+n)\widetilde{O}(m+n).

Correctness

This section is devoted to proving the correctness of Algorithm 5. For the sake of analysis, fix PP an arbitrary diametral shortest path. Consider the recursion tree T\mathcal{T} of an uncapped trial of Algorithm 5, whose nodes are recursive instances and whose edges connect each child to the parent that called it. Let TP\mathcal{T}_P be the subtree of T\mathcal{T} induced by the recursive instances HH for which P[V(H)]≠∅P[V(H)]\ne\varnothing—by Lemma 1 each such instance contains a contiguous subpath of PP. All content below assumes that (H,P′=P[V(H)])(H,P'=P[V(H)]) is a node of TP\mathcal{T}_P, where P′P' is the non-empty, contiguous subpath of PP contained entirely in HH.

Recall that a vertex vv is called a bridge of a path QQ when v⇝Qv\leadsto Q and Q⇝vQ\leadsto v. We call a node (H,P′)(H,P') of TP\mathcal{T}_P bridged, if a sampled pivot is a bridge of P′P'. Furthermore, a node (H,P′)(H,P') is small, if ∣RH(P′)∣≤D|R_H(P')|\le D, and large otherwise.

Now, starting at the root prune TP\mathcal{T}_P in a depth-first manner, stopping each branch at the first small or bridged node (hereafter we use TP\mathcal{T}_P to refer to the pruned tree, otherwise known as the subproblem tree). Along with Observation 1, the following lemma establishes the mechanisms by which small and bridged nodes of TP\mathcal{T}_P reveal the length of the subpath of PP they contain.

Lemma 5. If (H,P′=p1,…,p∣P′∣)(H,P'=p_1,\ldots,p_{|P'|}) is small, then with probability at least ∣V(P′)∣/(2D)|V(P')|/(2D), Algorithm 5 observes an original distance in the base input graph at least d(P′)/2d(P')/2 during the Sweep⁡\operatorname{Sweep} phase.

Proof. Recall that the least ancestor aa of P′P' is the first uncolored member of P′P'’s in-relevance RH−(P′)R_H^-(P') encountered during the execution of Sweep⁡\operatorname{Sweep}. By contradiction with aa’s minimality, both aa and P′P' must be uncolored at the moment that aa is encountered, otherwise they would have been discovered by search from an ancestor earlier in the execution. Thus, if a∈{p1,…,p⌈∣P′∣/2⌉}a\in\{p_1,\ldots,p_{\lceil|P'|/2\rceil}\}, then Sweep⁡\operatorname{Sweep} observes d(a,p∣P′∣)≥d(P′)/2d(a,p_{|P'|})\ge d(P')/2 during BFS rooted at aa. By Propositions 2.1–2.2 of [5], the

Algorithm 5 ReachDiam(GG).

Input: Digraph GG with nn vertices.

Output: Estimate D^\widehat{D} to the reachability diameter DD of GG.

Procedure: ReachDiam(GG).

  1. Base case: if ∣E(G)∣=0|E(G)| = 0, return 0.

  2. Repeat Recurse(GG, 0) for O(log⁡n)O(\log n) trials, throwing out each trial exceeding c1(m+n)log⁡c2(n+2)c_1(m + n) \log^{c_2}(n + 2) computation steps, where c1,c2c_1, c_2 are large enough constants.

  3. Return the maximum of 1 and the values reported by Recurse.

Procedure: Recurse(HH, rr).

Here rr denotes the recursion level.

  1. Base case: if ∣E(H)∣=0|E(H)| = 0, return 0.

  2. Sweep(HH).

  3. Sample S⊆V(H)S \subseteq V(H) independently with probability:

pr←min⁡{1,20Θ(log⁡n)r+1log⁡(n)/n}.p_r \leftarrow\min\{1, 20\Theta(\log n)^{r+1}\log(n)/n\}.
  1. For each s∈Ss \in S, run forward and backward BFS starting at ss in the original HH. The vertices RH+(s)∩RH−(s)R_H^+(s) \cap R_H^-(s) seen in both searches are omitted in subsequent steps.

  2. Group the remaining vertices into sets V1,…V_1, \ldots according to their reachability signatures:

σ(v):=(1[v⇝s],1[s⇝v])s∈S.\sigma(v) := \left(1[v \rightsquigarrow s], 1[s \rightsquigarrow v]\right)_{s\in S}.
  1. For each ViV_i, Recurse(H[Vi]H[V_i], r+1r + 1).

  2. Return the maximum of 1, the value reported by Sweep, the largest depth of any search, and the values reported by recursive calls.

least ancestor aa of P′P' is distributed uniformly at random on RH−(P′)R_H^-(P'). Therefore, the probability that a∈{p1,…,p⌈∣P′∣/2⌉}a \in\{p_1, \ldots, p_{\lceil|P'|/2\rceil}\} is exactly:

⌈∣P′∣/2⌉∣RH−(P′)∣≥∣V(P′)∣2∣RH−(P′)∣≥∣V(P′)∣2D≥d(P′)2D.\frac{\lceil|P'|/2\rceil}{|R_H^-(P')|} \ge\frac{|V(P')|}{2|R_H^-(P')|} \ge\frac{|V(P')|}{2D} \ge\frac{d(P')}{2D}.

where we use the fact that (H,P′)(H, P') is small to bound RH−(P′)≤RH(P′)≤DR_H^-(P') \le R_H(P') \le D. To complete the proof we show that every distance reported by Sweep is a real distance in the input graph, Consider that after each search the colored set of Sweep is closed under reachability by definition, and by consequence the uncolored set contains every dipath in HH between every ordered pair of remaining endpoints. In other words, the value reported by Sweep is an original distance in HH, which is an original distance in the base input graph GG by Lemma 1.

Thus, all we need is a small or bridged node which contains a significant length of the original diametral path PP (provided that the probability guarantee is justified). Vertices of PP are only removed from the recursion in the children of bridged nodes (Step 4), so the set of leaves F⊆V(TP)\mathcal{F} \subseteq V(T_P) partitions V(P)V(P). In particular, d(P)=∑i=1∣F∣d(Pi)+(∣F∣−1)d(P)=\sum_{i=1}^{|\mathcal{F}|}d(P_i)+(|\mathcal{F}|-1), where F={(H1,P1′),…}\mathcal{F}=\{(H_1,P'_1),\ldots\}. We call F\mathcal{F} the frontier. The analysis of [2] bounds the cardinality of the frontier.

Lemma 6. ∣F∣≤1+O(log⁡2n)n1/2+o(1)D|\mathcal{F}|\le1+O(\log^2 n)\frac{n^{1/2+o(1)}}{\sqrt{D}}, with probability at least 3/43/4.

Proof. Let XX be the random variable counting the number of large nodes in TP\mathcal{T}_P. By Lemma 2 with x=Dx=D,

E[X]≤n1/2+o(1)D,\mathbb{E}[X]\le\frac{n^{1/2+o(1)}}{\sqrt{D}},

and Pr⁡[X≤8⋅n1/2+o(1)D]≥1−1/8\Pr[X\le8\cdot\frac{n^{1/2+o(1)}}{\sqrt{D}}]\ge1-1/8 by Markov.

By construction, every non-root frontier node has a large parent in TP\mathcal{T}_P. Moreover, by the second guarantee of Lemma 2, every large node has O(log⁡2n)O(\log^2 n) children in TP\mathcal{T}_P with probability at least 1−O(n−10)1-O(n^{-10}). Thus:

∣F∣≤1+8⋅O(log⁡2n)n1/2+o(1)D,|\mathcal{F}|\le1+8\cdot O(\log^2 n)\frac{n^{1/2+o(1)}}{\sqrt{D}},

with probability at least 1−1/8−O(n−10)≥3/41-1/8-O(n^{-10})\ge3/4, as desired.

We are now ready to complete the proof of Theorem 1.

Proof. Assume D≥1D\ge1, since the case D=0D=0 is trivial. The frontier partitions the diametral shortest path PP into contiguous subpaths, separated by ∣F∣−1|\mathcal{F}|-1 connecting edges. Thus, when DD is sufficiently larger than ∣F∣|\mathcal{F}|, some frontier subpath must have length Ω(D/∣F∣)\Omega(D/|\mathcal{F}|). If such a subpath belongs to a bridged node, Observation 1 guarantees that the algorithm observes at least half its length, which gives the desired estimate.

For a small node, Lemma 5 gives a probability of observing half its subpath length that is proportional to the length of its subpath. A single long subpath may have a small success probability. However, if we have sufficiently many small nodes containing subpaths that are long enough, they collectively give a constant probability of success. We establish this by showing that short subpaths and connecting edges cannot account for too much of PP.

More precisely, condition on the pivot samples, F\mathcal{F} is fixed while the sweeps remain independent. If D≤4∣F∣D\le4|\mathcal{F}|, the algorithm already reports at least 1≥D/(4∣F∣)1\ge D/(4|\mathcal{F}|). We then assume D>4∣F∣D>4|\mathcal{F}|, so that the connecting edges contribute less than D/4D/4.

Next, we choose a target tt so that the subpaths of length at most 2t2t contribute at most another D/4D/4 in total. Specifically, set t=D/(8∣F∣)t=D/(8|\mathcal{F}|), and call a frontier node (H,P′)(H,P') short if d(P′)≤2td(P')\le2t, and long otherwise. The short nodes contain total path length at most 2t∣F∣=D/42t|\mathcal{F}|=D/4. Since ∑(H,P′)∈Fd(P′)=D−(∣F∣−1)\sum_{(H,P')\in\mathcal{F}}d(P')=D-(|\mathcal{F}|-1), the long nodes contain total path length at least:

∑(H,P′)∈Fd(P′)>2td(P′)≥D−(∣F∣−1)−2t∣F∣≥D2.\sum_{\substack{(H,P')\in\mathcal{F}\\d(P')>2t}}d(P')\ge D-(|\mathcal{F}|-1)-2t|\mathcal{F}|\ge\frac{D}{2}.

If any long node is bridged, Observation 1 guarantees an observed distance of at least d(P′)/2>td(P')/2>t. Otherwise, every long node is small. For each such node, Lemma 5 guarantees that its sweep observes a distance at least d(P′)/2>td(P')/2>t with probability at least ∣V(P′)∣/(2D)≥d(P′)/(2D)|V(P')|/(2D)\ge d(P')/(2D). The probability that all these sweeps fail to observe a distance at least tt is at most:

∏(H,P′)∈Fd(P′)>2t(1−d(P′)2D)≤exp⁡(−12D∑(H,P′)∈Fd(P′)>2td(P′))≤e−1/4.\prod_{\substack{(H,P')\in\mathcal{F}\\d(P')>2t}}\left(1-\frac{d(P')}{2D}\right) \leq\exp\left(-\frac{1}{2D}\sum_{\substack{(H,P')\in\mathcal{F}\\d(P')>2t}}d(P')\right) \leq e^{-1/4}.

Thus, for every fixed choice of pivot samples, the algorithm reports at least D/(8∣F∣)D/(8|\mathcal{F}|) with probability at least 1−e−1/41-e^{-1/4}.

By Lemma 6, with probability at least 3/43/4 over the pivot samples, the size of the frontier is bounded by: ∣F∣≤1+O(log⁡2n)n1/2+o(1)/D|\mathcal{F}|\leq1+O(\log^2 n)n^{1/2+o(1)}/\sqrt{D}. Combining these bounds, a single execution reports a distance at least:

D8(1+O(log⁡2n)n1/2+o(1)D).\frac{D}{8\left(1+O(\log^2 n)\frac{n^{1/2+o(1)}}{\sqrt{D}}\right)}.

with probability at least 34(1−e−1/4)\frac{3}{4}(1-e^{-1/4}). Since a trial is stopped by exceeding its computation budget with probability O(n−10)O(n^{-10}), a capped trial succeeds with probability at least 34(1−e−1/4)−O(n−10)\frac{3}{4}(1-e^{-1/4})-O(n^{-10}), which remains bounded below by a positive constant. Thus, after O(log⁡n)O(\log n) independent repetitions, taking the maximum reported value gives an estimate D^\widehat{D} satisfying the same lower bound with high probability.

If D≤n1/3D\leq n^{1/3}, the bound D^≥1\widehat{D}\geq1 immediately gives D/D^≤n1/3D/\widehat{D}\leq n^{1/3}. Otherwise, D>n1/3D>n^{1/3}, and the preceding bound gives:

DD^≤8(1+O(log⁡2n)n1/2+o(1)D)≤n1/3+o(1).\frac{D}{\widehat{D}}\leq8\left(1+O(\log^2 n)\frac{n^{1/2+o(1)}}{\sqrt{D}}\right)\leq n^{1/3+o(1)}.

Moreover, Lemma 1 guarantees that every reported distance is a distance in the base graph, so D^≤D\widehat{D}\leq D, which completes the proof.

References

  1. [1]Amir Abboud, Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. 2023. On Diameter Approximation in Directed Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 274). Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2:1–2:17. doi:10.4230/LIPIcs.ESA.2023.2DOI
  2. [2]Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. 2026. Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth. arXiv:2605.03892 [cs.DS] https://arxiv.org/abs/2605.03892
  3. [3]Ben Bals, Joakim Blikstad, Daniel Dadush, Yasamin Nazari, and Jonas Schmidt. 2026. Revisiting Diameter in Directed Graphs. arXiv:2606.08217v1 [cs.DS] https://arxiv.org/abs/2606.08217v1
  4. [4]Greg Bodwin and Gary Hoppenworth. 2024. Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. arXiv:2304.02193v3 [cs.DS] https://arxiv.org/abs/2304.02193v3 Version 3; first posted in 2023.
  5. [5]Edith Cohen. 1997. Size-Estimation Framework with Applications to Transitive Closure and Reachability. J. Comput. System Sci. 55, 3 (1997), 441–453. doi:10.1006/jcss.1997.1534DOI
  6. [6]Don Coppersmith and Michael Elkin. 2006. Sparse Sourcewise and Pairwise Distance Preservers. SIAM Journal on Discrete Mathematics 20, 2 (2006), 463–501. doi:10.1137/050630696DOI
  7. [7]Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. 2022. Hardness of Approximate Diameter: Now for Undirected Graphs. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Piscataway, NJ, USA, 1021–1032. doi:10.1109/FOCS52979.2021.00102DOI
  8. [8]Friedrich Eisenbrand and Gennady Shmonin. 2006. Coraththeodory Bounds for Integer Cones. Operations Research Letters 34, 5 (2006), 564–568. doi:10.1016/j.orl.2005.09.008DOI
  9. [9]Jeremy T. Fineman. 2018. Nearly Work-Efficient Parallel Algorithm for Digraph Reachability. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’18). Association for Computing Machinery, New York, NY, USA, 457–470. doi:10.1145/3188745.3188926arxiv.org/abs/1711.01700
  10. [11]William Hesse. 2003. Directed Graphs Requiring Large Numbers of Shortcuts. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’03). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 665–669. https://dl.acm.org/citation.cfm?id=644108.644216DOI
  11. [12]Shang-En Huang and Seth Pettie. 2018. Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 101), David Eppstein (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 26:1–26:12. doi:10.4230/LIPIcs.SWAT.2018.26DOI
  12. [13]Arun Jambulapati, Yang P. Liu, and Aaron Sidford. 2019. Parallel Reachability in Almost Linear Work and Square Root Depth. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA, 1664–1686. doi:10.1109/FOCS.2019.00098DOI
  13. [14]C. S. Karthik and Pasin Manurangsi. 2020. On Closest Pair in Euclidean Metric: Monochromatic Is as Hard as Bichromatic. Combinatorica 40, 4 (2020), 539–573. doi:10.1007/s00493-019-4113-1DOI
  14. [15]Shimon Kogan and Merav Parter. 2022. New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the O(√n) Barrier. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1326–1341. doi:10.1137/1.9781611977073.55
  15. [16]Shimon Kogan and Merav Parter. 2023. Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 212–239. doi:10.1137/1.9781611977554.ch9
  16. [17]Marvin Künnemann. 2022. A Tight (non-Combinatorial) Conditional Lower Bound for Klee’s Measure Problem in 3D. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA, 555–566. doi:10.1109/FOCS54457.2022.00059DOI
  17. [18]Liam Roditty and Virginia Vassilevska Williams. 2013. Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC ’13). Association for Computing Machinery, New York, NY, USA, 515–524. doi:10.1145/2488608.2488673
  18. [19]Aviad Rubinstein. 2018. Hardness of Approximate Nearest Neighbor Search. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’18). Association for Computing Machinery, New York, NY, USA, 1260–1268. doi:10.1145/3188745.3188916DOI
  19. [20]Gennady Shmonin. 2007. Parameterised Integer Programming, Integer Cones, and Related Problems. Ph.D. Dissertation. Universität Paderborn. https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/Shmonin2007.pdf
  20. [21]Mikkel Thorup. 1993. On Shortcutting Digraphs. In Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (Lecture Notes in Computer Science, Vol. 657). Springer, Berlin, Heidelberg, 205–211. doi:10.1007/3-540-56402-0_48DOI
  21. [22]Jeffrey D. Ullman and Mihalis Yannakakis. 1991. High-Probability Parallel Transitive-Closure Algorithms. SIAM J. Comput. 20, 1 (1991), 100–125. doi:10.1137/0220006DOI

Paper details

vlnc:W_r5nw2uzg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6, 6.1

View statement
Looking for related papers…
Contents