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 -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 , with high probability, in time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an -approximation in time for every fixed , establishing the necessity of polynomial loss for nearly-linear time algorithms.
Introduction
The reachability diameter of a graph is the maximum -to- shortest-path distance across all pairs such that is reachable from . 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, and denote respectively the numbers of vertices and edges, and a -approximation to the reachability diameter is an estimate satisfying . They give an -approximation algorithm running in nearly-linear 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 , 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.
Table 1. Reachability diameter approximation in near-linear time. Upper bounds correspond to -time algorithms, lower bounds mean an approximation factor is excluded under the listed hypothesis, for fixed . For randomized HC the bound holds for algorithms with at least success rate.
The barrier. The -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 hopbound. Improving the approximation factor requires going beyond what this hopbound directly implies. We recall the construction: given an input unweighted digraph, sample vertices called pivots uniformly at random without replacement. Run BFS from each pivot and include the edge for each other pivot reachable from . 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 pivot samples the construction adds only edges, and the reachability diameter of the augmented graph is bounded by .
To see how estimating reachability diameter inherits the folklore 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 -approximation to the reachability diameter. To see why, condition on the high-probability event described above, and let be a fixed diametral path. The construction partitions into at most 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 . If this segment corresponds to a shortcut edge , BFS initiated at reports the distance exactly. The limitation of this approach is the cost of search, yielding an 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 reachability diameter with running time and 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 nearly matches the folklore algorithm’s. For a fixed path , instead of a pivot near each endpoint being used to shortcut the middle segment, the JLS algorithm partitions the graph, which fragments , 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 over the course of the recursion is at most . 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 -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 benchmark into reachability diameter estimation, making it an apparent barrier for this problem as well.
Further developments in shortcut sets emphasize as a significant benchmark. Kogan and Parter achieve a substantially smaller hopbound of [15], but their construction takes superlinear time [16]. Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak [2] retain near-linear work and improve the reachability diameter to on dense graphs allowing shortcut edges, where is the matrix multiplication exponent. However, their guarantee remains on sparse graphs. This motivates the following refinement of the question of [3]:
Problem 1. Can reachability diameter estimation overcome in better-than-matrix-multiplication time, without a corresponding improvement in shortcut construction?
We answer this question in the affirmative, giving a randomized -time algorithm that achieves an -approximation with high probability.
Theorem 1. There is a randomized algorithm computing a -approximation to the reachability diameter of an unweighted digraph with high probability, running in 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 approximation barrier for reachability diameter. The algorithm and proof are given in § 4.
Polynomial approximation loss. Beyond breaking the 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 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 , there is no deterministic -time algorithm that, on every unweighted digraph with vertices, edges, and reachability diameter , returns an estimate satisfying
Under the randomized version of the hypothesis, there is no randomized -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 . 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 be the input unweighted digraph, with vertices and edges. Our algorithm proceeds by recursive partitioning; to differentiate the base input graph from the input to an arbitrary recursive subproblem we write for the latter, where is a subgraph of .
For , the function is the shortest-path distance in , even when and belong to a recursive subproblem. In particular, when there is no directed -to- path in , and . For a dipath , we denote by the restriction of to . When is a shortest dipath in , we use to refer to the endpoint to endpoint distance .
In any recursive instance with input and , we write when there exists a directed -to- path through , including dipaths consisting of a single vertex, so . When the relevant graph is clear from context, we simply say . The out-relevance of , also called the descendants of in , is the subset of which is reachable from , or equivalently, the set of vertices discovered during BFS initiated at on . Symmetrically, the in-relevance (ancestors) of in , , is the set of vertices discovered during reverse BFS: BFS with all edge directions reversed. The union is called the relevance. The size, or cardinality of these sets is denoted: . For a dipath lying in , the relevance is , and similarly we have: , and . When is a set of vertices, is the subgraph of induced by .
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 . 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 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 -partite hypergraph whose vertex set is partitioned into disjoint parts , each containing vertices. Every hyperedge contains vertices from three distinct parts. A -hyperclique is a set of 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 and constant , there is no deterministic algorithm deciding whether a 3-uniform -partite hypergraph with vertices in each part has a -hyperclique in time. The randomized version asserts the same for randomized algorithms with error probability at most on every input.
Label the vertices in each part by , and let specify the vertex selected from . Consider any three vertices from distinct parts that do not form a hyperedge. Since a -hyperclique cannot contain all three vertices, we impose the constraint . Let be the collection of all constraints obtained in this way. Then . Trivially, we have
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 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 . We connect its vertices in consecutive layers by constant-length dipaths. If the encoded assignment violates a constraint in , 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 be the input to an arbitrary instance at level of the recursion, where the root instance is at level .
Sampling: Sample pivots from uniformly at random with probability . The sampling probability grows by per recursion level, so after levels and every remaining vertex becomes a pivot.
Search: Run BFS and reverse BFS from each . Remove all vertices found in both search directions initiated at a pivot.
Labelling: Each pivot assigns every a reachability signature
where denotes the indicator function.
Grouping: Group the remaining vertices into sets according to their reachability signatures. The induced subgraphs are the inputs to the recursive children of .
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 and an associated pivot add the following edges to the shortcut set:
These edges preserve reachability by definition. Now fix some instance with input and pivot samples . Let be any -to- dipath in , . A pivot is called a bridge of when and . If such a pivot exists, then the shortcut edges and reduce the shortest -to- distance to at most two hops in the augmented graph. We therefore regard 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 levels, the sampling probability satisfies 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 be an unweighted digraph, and let be the input to any recursive instance obtained from by repeated JLS partitioning. Then:
For every directed path in , the restriction is either empty or consists of a contiguous subpath of .
For every , the shortest-path distance from to in equals , their shortest-path distance in .
Proof. The base case is immediate. Now suppose that an arbitrary instance with input satisfies both given statements. We proceed by induction on the recursive subproblems . By way of contradiction, suppose that , all different, such that there is a -to- directed path in containing , but after partitioning end up in a different child than : and . The case where is dropped after the searching phase is immediate, if there exists some pivot such that is found in both of its search directions then and are also found in both searches, and dropped. Since and belong to the vertices of the same child they have identical reachability signatures. Meaning that, for every sampled pivot , we have and . These implications force and to have exactly the same labels as , 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 is grouped into the same child. By induction, every directed path in , the restriction is either empty or consists of a contiguous subpath of . Moreover, for every , the shortest-path distance from to in equals , their shortest-path distance in .
Observation 1 (Observation 21 and Corollary 23 of Bals et al. [3]). Let and be as in Lemma 1. Then for , the shortest-path distance from to in equals their shortest-path distance in . In other words, if is finite, then contains some -to- dipath of length . Fix some such , and suppose that we sample a bridge of in the recursive instance corresponding to input , so and . By another application of Lemma 1, BFS and reverse BFS from in the search phase of JLS partitioning reveal and . The triangle inequality gives: . Thus, resolving reveals a distance at least half its length, without overestimating the reachability diameter of .
This observation explains how Bals et al. acquire distance estimates from resolved fragments, inheriting the 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().
Input: Recursive instance .
Output: An original distance in the base input graph to ReachDiam.
Process the initially uncolored vertices 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).
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 .
To see why Sweep works to detect distance in unresolved fragments: let be the input to any recursive instance obtained from by repeated JLS partitioning, such that contains a shortest dipath with in-relevance . Suppose that we do not sample a bridge of in the current instance, i.e. is unresolved in this exercise. First, we naturally extend the definition of least-rank ancestor to dipaths 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 of is distributed uniformly at random over . Additionally, and every vertex of are uncolored at the moment when is encountered in the ordering, otherwise we must have already processed an ancestor of , a contradiction with ’s minimality. Now consider the event that is one of the vertices lying on the first half of , called witnesses. Then BFS rooted at reveals the length of the -to- subpath of , which is at least half the length of . By Lemma 1, the length of in is equal to the shortest-path distance in , 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 , and therefore all paths between uncolored vertices are themselves uncolored, meaning that BFS distances reported by Sweep equal their distances in , hence . 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 is uniformly random over , so the probability that lies on the first half of is exactly the ratio of the number of witnesses , to the total size of ’s in-relevance in .
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 be the input to JLS partitioning, and a fixed shortest dipath in . By Lemma 1, every recursive instance whose input subgraph contains vertices of contains a contiguous subpath of . Now consider the subproblem tree of , 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 has large relevance:
Lemma 2 (Adapted from Lemma 4.5 and Observation 4.6 in [2]). Fix a shortest path in the input to JLS partitioning, and a threshold . Let be the count of nodes in the subproblem tree of whose associated fragment satisfies , where is the corresponding recursive input. Then:
Moreover, with probability at least , every node in the subproblem tree of has 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 , either through a sampled bridge or Sweep, achieving the desired sub- 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 and constraints .
Main ideas and graph construction framework
Encoding candidate assignments in the graph. We now explain how to encode the candidate assignments for in our layered graph. At a high level, each trajectory in the graph encodes an assignment to the variables .
We begin by outlining the graph construction. Consider a vertex represented by the coordinates , where denotes its layer and gives its coordinates within that layer. Now, consider two vertices and with . If is an integer for every , we can obtain the second endpoint from the first by advancing one layer at a time and changing the -th coordinate by exactly 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 , the direction is . Let denote the intercept of the pair. By fixing and , each valid pair determines dipaths starting from 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 and . Hence, all the information carried by a trajectory is contained in and , so encoding an assignment in a trajectory amounts to encoding it in these two vectors. In the meanwhile, the number of possible choices of and determines how many distinct trajectories we can use. By assigning different blocks to different variables, we can distribute the values of across the starting coordinates and the direction components . Thus, we ensure that every candidate assignment to 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 satisfying every constraint in .
Consider any valid pair in the digraph. The two vertices uniquely determine the intercept and direction of the corresponding trajectory. Starting from and moving in direction from one layer to the next, we obtain a unique vertex in each layer . 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 and encodes an assignment that violates a constraint in , 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 be a power of two, and denote the total number of layers. For each length , we choose the intervals , where is a nonnegative integer. For example, when , we choose . 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 dyadic intervals. To see this, consider any interval . Start with the unit intervals between and , 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 dyadic intervals.
In conclusion, we only need to construct constant-length shortcuts for the aligned dyadic intervals in to obtain short paths between every pair of vertices on a failing trajectory.
Protecting a satisfying trajectory. Consider a trajectory determined by the intercept and direction . Suppose its encoded assignment satisfies every constraint in , and such trajectory is a satisfying trajectory. We want the distance from its vertex in layer to its vertex in layer 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 from one layer to the next changes by . We add a coordinate to each vertex, called the energy coordinate. For every move in direction between consecutive layers, we require to increase by . Just as gives the coordinates in layer 0, let denote the value of in layer 0. Starting from and applying these changes from one layer to the next, we obtain the vertex on the trajectory in layer with coordinates
Thus, with the energy coordinate included, , , and determine a trajectory.
Recall that a constant-length shortcut between any two vertices on this trajectory also follows direction . If a constant-length shortcut is added between two vertices on this trajectory in layers , we require the total increase in along the shortcut to be . Thus, the energy coordinate changes from to , exactly as it would when moving in direction 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 , , and , 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 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 be the directions of these segments. For segment , let be the difference between the layer indices of its first and last vertices.
Thus, segment changes by and by . Let be the difference between the layers of the two fixed vertices. Since both vertices lie on the trajectory with direction , the total changes in and must also be and , respectively. Hence,
Consequently,
Every term in the sum is nonnegative, and every is positive. Hence, for every segment . 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 , 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 , the direction , and to specify a trajectory. We also use to encode some part of the variables from , just as how we use the and . 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 in the intercept , the direction , and . We have not yet specified how many coordinates has. Since and each have one component for every coordinate of , 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, , together with the energy coordinate , so that and 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 on and
Choose bounded ranges for and the direction .
Create vertices in layers , with coordinates restricted to the chosen ranges.
Encode each assignment to in , , and .
Connect vertices on the same trajectory in consecutive layers: .
for each dyadic interval with do
For a failing trajectory, add a shortcut between vertices in layers and : .
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 .
First, we will specify the coordinate ranges.
Choosing the coordinate ranges. Let be the number of choices for each direction component, so that for each . Recall that advancing one layer increases by and by . Over layers, each increases by less than , and increases by less than . Thus, if we choose and , every vertex on the trajectory from layer 0 to layer satisfies and .
In each layer , we create all vertices with integer coordinates satisfying for and . We call them base vertices to distinguish them from the auxiliary vertices introduced later. For convenience, write and let denote the set of allowed coordinates : . In particular, .
Connecting consecutive layers. Consider a base vertex in layer . There are choices of , so adding a separate edge for every direction would be too expensive.
Instead, we introduce two auxiliary layers between layers and , each containing one vertex for every . We add edges from layer to the first auxiliary layer, then to the second auxiliary layer, and finally to layer . The -th edge of each resulting three-edge dipath chooses and updates only and . More specifically, the -th edge updates to and to .
A three-edge dipath combines one choice of , one of , and one of . These combinations represent all directions without requiring us to enumerate them explicitly when constructing the edges. Thus, each vertex needs only choices for its outgoing edges. Moreover, the three-edge dipath gives the required total changes in and . Conversely, consider two base vertices on the same trajectory in consecutive layers, with . 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 .
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 with , we add a constant-length shortcut in a similar way with changes and in and . 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 , , and separately. When constructing the edge that chooses , we can recover , and decode the variables stored in and . How can these variables collectively determine whether the complete assignment violates a constraint in without exhaustive enumeration?
Note that an assignment is failing if it violates at least one constraint in . Thus, we can test the constraints separately. For each , 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 . Thus, a failing assignment only needs to allow a dipath through one of these channels.
To violate , all three variables involved in must equal their corresponding forbidden values. When constructing an edge that chooses , we check every variable of stored in or , and add the edge only if all their decoded values match the forbidden values specified by . If neither nor stores a variable of , we keep the edge without imposing any condition from . 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 stored in or has its forbidden value.
To ensure that a complete dipath is available only when is violated, we must also check any variables of stored in . We explain how to perform this remaining check next.
Unlike , the value of depends on all three direction components since . We cannot recover from the choice of a single component of the direction. Instead, we guess the energy coordinate of the base vertex in layer . Together with the energy coordinate of the base vertex in layer , this guess determines . On the edge leaving the base vertex in layer , we use the resulting value of to check the variables of stored in . On the edge entering the base vertex in layer , we require the energy coordinate reached by that edge to equal the guess.
To see why this works, write , where is a non-negative integer. Let and denote the energy coordinates of the two base vertices in layers and , respectively. A complete three-edge dipath satisfies , so
We now explain how to modify the graph construction accordingly. For each , create a separate channel for every integer guess of . On the edge leaving layer , use as the value of and require all variables of stored there to equal their forbidden values. On the edge entering layer , we require the energy coordinate of the base vertex reached by the shortcut to equal the guessed value . Since channels for different guesses have separate auxiliary vertices, the guess verified at layer must be the same one used to compute on the edge leaving layer . Thus, a complete three-edge dipath through the channel guarantees that the variables of stored in were checked using the correct value of .
Now, consider two base vertices on the same trajectory in layers and , with . If the trajectory is failing, choose a constraint violated by its encoded assignment. The channel corresponding to and the energy guess then passes all checks and provides a three-edge shortcut between the two vertices. Conversely, a complete dipath through the channel corresponding to and guarantees that and that the encoded assignment violates . Thus, these channels provide shortcuts precisely for failing trajectories. This construction uses 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 takes a value in , so one base- digit suffices to store it. For each trajectory, we write each component of and , as well as , in base and use the resulting digits to encode a unique assignment to .
We now choose and and specify how many variables to encode in each of these components. Since must be a power of two for the dyadic intervals, let be the smallest power of two at least , so that . Choose and , where and are positive integer constants to be fixed in Section 3.6. Then the bounds for each and for are polynomial in .
Since , each direction component can store at least variables from . Similarly, each intercept component can store variable values because . The energy coordinate in layer 0 can store variable values since .
Thus, to store all the variables in , we let . Assign in order to the base- digits of , using digits in each , digits in each , and digits in . 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 , form each , , and by placing the values of its assigned variables in these fixed digit positions. The resulting integers satisfy , , and . Hence, every candidate assignment is represented by a trajectory in the graph.
In the next subsection, we change how variables are encoded in by using the Chinese remainder theorem so that checking requires guessing only the energy information needed to read the variables of stored in . This will further decrease the size of the constructed graph and give us a stronger reduction.
Algorithm 3 Detailed graph construction
Input: , , , constraints , and the digit decoder
Create all base vertices with and . ▷ Connect vertices on the same trajectory in consecutive layers.
for each unit interval do
Create two copies of as auxiliary layers between layers and .
For each , , add .
For each , , add .
For each , , add .
end for ▷ Add constant-length shortcuts across dyadic intervals for failing trajectories.
for each dyadic interval with and do
for each and integer guess do
Create two copies of as auxiliary layers for each and .
for each , , and do
if then
If every variable of encoded in , , or equals its forbidden value, add .
else if then
If every variable of encoded in or equals its forbidden value, add .
else if then
If every variable of encoded in or equals its forbidden value and , add .
end if
end for
end for
end for
Compressing the energy encoding with the Chinese remainder theorem
Recall that, for each constraint and dyadic interval with , the previous construction creates a separate channel for every possible energy coordinate of the base vertex in layer . This requires guesses and two auxiliary layers for each guess. However, involves only three variables, and we only need the information that determines the values of those stored in . Intuitively, if we could divide the energy coordinate encoding into parts that can be read independently, then checking 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 , the Chinese remainder theorem states that any prescribed remainders modulo these primes determine a unique integer between and . Thus, we can encode an assignment to by prescribing remainders that represent its variable values. These remainders then uniquely determine an energy coordinate in the range .
Recall that the energy coordinate in layer stores of the variables . To change how these variables are encoded, we need the remainders to represent every possible assignment to these 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 distinct primes and use the remainders to encode the variables stored in , in the same order as in the previous encoding. Since each prime satisfies , so its possible remainders include all the variable values in .
Since is fixed, the prime number theorem guarantees that contains at least distinct primes for all sufficiently large . Recall that and , so these primes satisfy
Thus, by the Chinese remainder theorem, for any assignment to the variables stored in , there exists an integer such that each remainder equals the prescribed value of the variable encoded by that remainder.
We keep the encodings of and unchanged, so the chosen components satisfy and . For every layer , the corresponding coordinates therefore satisfy
Thus, every base vertex on this trajectory from layer to layer belongs to the graph, which means every candidate assignment to has such a trajectory representation.
Once the primes are fixed, we read the value of the variable assigned with respect to as . The final reduction modulo ensures that the value belongs to .
Checking constraints using energy remainders. For a constraint , let be the product of all primes for which the remainder encodes a variable of . If no variable of is stored in , let .
Now, consider a dyadic interval with and . To construct a constant-length shortcut, instead of guessing the entire energy coordinate in layer , we guess only its remainder . To see this, suppose that the energy coordinate in layer is . Then, we have
Thus, by guessing , it is enough to check the variables of stored in .
We now modify the construction of the constant-length shortcuts accordingly. For each and each guessed remainder , create two copies of as auxiliary layers between layers and . As before, a dipath through these auxiliary layers chooses on its three edges, respectively. The edge choosing changes to and to . When choosing , we check that every variable of stored in or equals its forbidden value.
On the edge from layer to the first auxiliary layer, use as the to read the variables of stored in . Add the edge whenever no variable of stored in , , and 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 stored in or differs from its forbidden value. Add an edge from the second auxiliary layer to a base vertex in layer if no variable of stored in or differs from its forbidden value and the energy coordinate of that base vertex satisfies .
New construction analysis. Fix a constraint , we now only need pairs of auxiliary layers instead of . Since involves only three variables, is a product of at most three primes. Hence, . Since , we have .
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
Choose distinct primes .
Add constant-length shortcuts across dyadic intervals for failing trajectories.
for each dyadic interval with and do
for each and guessed remainder do
Create two copies of as auxiliary layers for between layers and .
for each , , and do
Let .
if then
If no variable of encoded in , , or differs from its forbidden value, add
.
else if then
If no variable of encoded in or differs from its forbidden value, add
.
else if then
If and no variable of encoded in or differs from its forbidden value, add
.
end if
end for
end for
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 . 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 and be a valid pair on the trajectory with direction , with in an earlier layer than . Every dipath from to always follows direction when moving through consecutive layers and or using a shortcut.
Proof. Consider any dipath from to . 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 -th pair of successive base vertices, let be the direction chosen by the three edges between them, and let be the difference between their layers. The three edges together increase by and by . Thus, (2) gives for every .
Lemma 4 (Diameter gap). Let denote the reachability diameter of the constructed digraph by Algorithm 3 and Algorithm 4. If there is an assignment to satisfying every constraint in , then . Otherwise,
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 belong to the graph. Let and be its base vertices in layers and . The construction connects its vertices in consecutive layers by three-edge dipaths, giving a dipath of length from to $v.
By Lemma 3, every dipath from to 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 to uses only connections between consecutive layers. Each such connection has three edges, so .
When there is no satisfying assignment. Suppose now that every assignment violates a constraint in . We first consider two base vertices on the same trajectory, with for .
Since every assignment violates a constraint, this trajectory is failing. Consider a dyadic interval between the layers of the two fixed base vertices. If , choose a constraint violated by the trajectory’s assignment and , where is the energy coordinate of its base vertex in layer . By (4), the first edge reads the correct values of the variables of stored in . All the variable checks pass, and the last edge verifies . Hence, the two auxiliary layers for 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 dyadic intervals. Thus, concatenating the three-edge dipaths for these intervals gives a dipath of length at most .
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 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 and be distinct base vertices with a dipath from to . Suppose that there is a dipath from to that can be divided into segments of distinct direction . Thus, we have
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
where and are the -th coordinates of and , respectively. Since , , and , and all these differences are integers,
Starting at , advance by layers in direction for , in order. The total changes reach , and all coordinates are nondecreasing. Hence, the intermediate coordinates stay between those of and , within , so the construction provides the required dipath. By the preceding argument, the distance of each segment is at most . Concatenating these short dipaths gives .
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 vertices. There are base layers and two auxiliary layers for each of the pairs of consecutive layers. For each of the dyadic intervals of length at least two, we create two auxiliary layers for every constraint and guessed remainder . Thus, shortcuts across each such interval require 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 outgoing edges, one for each choice of the corresponding direction component. Thus, each pair of auxiliary layers contributes at most edges. Therefore,
To construct the graph, we first list the constraints in in time and find the required primes in by a sieve in time. We then create all base and auxiliary vertices and consider the choices of 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 and are fixed, all integers involved have bits, so each choice takes at most polylogarithmic time. The total construction time is therefore
Recall that , , , and . Substituting these values and from § 3.4 gives
These bounds explain why we changed the energy encoding in § 3.4. Guessing the entire energy coordinate would require pairs of auxiliary layers per dyadic interval of length at least two. The resulting construction-time bound would have exponent , exceeding . Guessing only the required remainder reduces the number of pairs to , whose exponent does not grow with the number of variables stored in .
Choosing the parameters and obtaining the exponent
We now choose and so that the reduction satisfies two requirements. First, constructing the graph and running a -time approximation algorithm must take time for some constant . 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 variables. By (9), constructing the graph and running the approximation algorithm together take time. Thus, the first requirement holds whenever , or equivalently, .
For the second requirement, consider an -approximation for a constant . By Lemma 4, if a satisfying assignment exists, the estimate is at least ; otherwise, it is at most . We therefore need . Since , , and , it suffices to choose
For fixed , this ratio increases with . We therefore take , the largest integer satisfying , and choose so that is positive. Then , and (9) becomes
At the same time, . For this choice of , the right-hand side of (10) satisfies
Thus, for every fixed , we can choose large enough that 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 in § 3.1. Suppose instead that has coordinates for a fixed integer . Both a connection between consecutive layers and a shortcut would use auxiliary layers, with the edges choosing separately. Each would store variables, each would store variables, and would still store variables. Thus, a trajectory would encode variables. Each would still range over . Since the energy increase across layers is less than , we would let range over . Each base or auxiliary layer would then contain vertices. The same counting argument therefore gives a vertex bound of and a construction-time bound of .
To keep the construction time polynomially smaller than , we would need . For fixed , the same diameter analysis gives a lower bound of when a satisfying assignment exists and an upper bound of otherwise. Taking and letting grow therefore gives the limiting approximation exponent . For every integer , this is at most , with equality only at : the inequality is equivalent to , which holds for and for all . Thus, three coordinates give the largest exponent for this construction under the size bounds above.
Upper Bound
Algorithm
Running time. Each call takes time. Recursive inputs at each of levels are vertex-disjoint, so the total running time of is . Together with Proposition 4.1 of [2], this implies that, for sufficiently large constants , an uncapped trial including the subroutine finishes within steps with probability . The worst case running time is .
Correctness
This section is devoted to proving the correctness of Algorithm 5. For the sake of analysis, fix an arbitrary diametral shortest path. Consider the recursion tree 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 be the subtree of induced by the recursive instances for which —by Lemma 1 each such instance contains a contiguous subpath of . All content below assumes that is a node of , where is the non-empty, contiguous subpath of contained entirely in .
Recall that a vertex is called a bridge of a path when and . We call a node of bridged, if a sampled pivot is a bridge of . Furthermore, a node is small, if , and large otherwise.
Now, starting at the root prune in a depth-first manner, stopping each branch at the first small or bridged node (hereafter we use 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 reveal the length of the subpath of they contain.
Lemma 5. If is small, then with probability at least , Algorithm 5 observes an original distance in the base input graph at least during the phase.
Proof. Recall that the least ancestor of is the first uncolored member of ’s in-relevance encountered during the execution of . By contradiction with ’s minimality, both and must be uncolored at the moment that is encountered, otherwise they would have been discovered by search from an ancestor earlier in the execution. Thus, if , then observes during BFS rooted at . By Propositions 2.1–2.2 of [5], the
Algorithm 5 ReachDiam().
Input: Digraph with vertices.
Output: Estimate to the reachability diameter of .
Procedure: ReachDiam().
Base case: if , return 0.
Repeat Recurse(, 0) for trials, throwing out each trial exceeding computation steps, where are large enough constants.
Return the maximum of 1 and the values reported by Recurse.
Procedure: Recurse(, ).
Here denotes the recursion level.
Base case: if , return 0.
Sweep().
Sample independently with probability:
For each , run forward and backward BFS starting at in the original . The vertices seen in both searches are omitted in subsequent steps.
Group the remaining vertices into sets according to their reachability signatures:
For each , Recurse(, ).
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 of is distributed uniformly at random on . Therefore, the probability that is exactly:
where we use the fact that is small to bound . 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 between every ordered pair of remaining endpoints. In other words, the value reported by Sweep is an original distance in , which is an original distance in the base input graph by Lemma 1.
Thus, all we need is a small or bridged node which contains a significant length of the original diametral path (provided that the probability guarantee is justified). Vertices of are only removed from the recursion in the children of bridged nodes (Step 4), so the set of leaves partitions . In particular, , where . We call the frontier. The analysis of [2] bounds the cardinality of the frontier.
Lemma 6. , with probability at least .
Proof. Let be the random variable counting the number of large nodes in . By Lemma 2 with ,
and by Markov.
By construction, every non-root frontier node has a large parent in . Moreover, by the second guarantee of Lemma 2, every large node has children in with probability at least . Thus:
with probability at least , as desired.
We are now ready to complete the proof of Theorem 1.
Proof. Assume , since the case is trivial. The frontier partitions the diametral shortest path into contiguous subpaths, separated by connecting edges. Thus, when is sufficiently larger than , some frontier subpath must have length . 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 .
More precisely, condition on the pivot samples, is fixed while the sweeps remain independent. If , the algorithm already reports at least . We then assume , so that the connecting edges contribute less than .
Next, we choose a target so that the subpaths of length at most contribute at most another in total. Specifically, set , and call a frontier node short if , and long otherwise. The short nodes contain total path length at most . Since , the long nodes contain total path length at least:
If any long node is bridged, Observation 1 guarantees an observed distance of at least . Otherwise, every long node is small. For each such node, Lemma 5 guarantees that its sweep observes a distance at least with probability at least . The probability that all these sweeps fail to observe a distance at least is at most:
Thus, for every fixed choice of pivot samples, the algorithm reports at least with probability at least .
By Lemma 6, with probability at least over the pivot samples, the size of the frontier is bounded by: . Combining these bounds, a single execution reports a distance at least:
with probability at least . Since a trial is stopped by exceeding its computation budget with probability , a capped trial succeeds with probability at least , which remains bounded below by a positive constant. Thus, after independent repetitions, taking the maximum reported value gives an estimate satisfying the same lower bound with high probability.
If , the bound immediately gives . Otherwise, , and the preceding bound gives:
Moreover, Lemma 1 guarantees that every reported distance is a distance in the base graph, so , which completes the proof.
References
- [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]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]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]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]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]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]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]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]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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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