A Black-Box Workload Barrier for Exact Girth via Multi-Scale Nearest-Source Estimation in CONGEST

Article

A Black-Box Workload Barrier for Exact Girth via Multi-Scale Nearest-Source Estimation in CONGEST Indraveni Chebolu 1 , Bhavani Singh Rajpurohit 1 1

*

and Arnab Mallick 1 *

Centre for Development of Advanced Computing Correspondence: arnabm@cdac.in

arXiv:2608.17358v1 [cs.DS] 18 Aug 2026

Abstract Recent multi-scale nearest-source methods give polynomially sublinear girth approximations in CONGEST. We isolate the direct black-box route for making this framework exact: sequential calls to the same estimator on fresh exchangeable source sets, with source cardinalities and nearest-source capacities chosen adaptively from previous scalar outputs and with an adaptive stopping rule. On a bounded-degree, logarithmic-diameter family Ht with nt vertices and a unique girth-gt = Θ(log nt ) cycle, exactness requires a sampled cycle source to survive at an antipodal edge despite a linear number of strictly closer competitors. For any such exactification A, a permutation-rank argument yields the implementation-independent workload bound Pr[A( Ht ) = gt ] ≤ (3gt /nt ) E[∑ Tj=1 min{ Q j , k j }], where T is the number of executed calls, Q j is the source-set cardinality, and k j is the nearest-source capacity of call j. Thus constant exactness probability requires Ω(nt /gt ) = Ω(nt / log nt ) expected retained-source workload. We formally show that retuning the recent multi-scale template solely through its scale count/order, Bernoulli or fixed-cardinality sampling, capacities, and scalar-output stopping rules lies in this class. For the standard sequential packetized estimator realization, the workload theorem gives an Ω(nt / log nt ) expected-round corollary. This is a barrier to a defined black-box exactification strategy, not a lower bound for unrestricted exact girth in CONGEST. Keywords: distributed algorithms; CONGEST; girth; source detection; randomized algorithms; sampling; lower bounds; algorithmic barriers

1. Introduction The girth of an undirected graph is the length of its shortest cycle. In the CONGEST model, exact girth can be computed in O(n) rounds by standard all-pairs shortest-path techniques, while the best known general exact bound that exploits the value of the girth is parameterized by g and becomes nearly linear as g grows [1,2]. The approximation landscape changed recently. Chechik, Lifshitz, and Mukhtar introduced a multi-scale nearest-source construction that gives an f -approximation e (n1/ f + D ) rounds for every constant integer f > 2 [3]. Their to unweighted undirected girth in O construction samples sources at several scales, retains bounded nearest-source breadth-first-search records, and invokes the same scalar girth estimator at each scale. A direct next question is whether this recently successful approximation template can be made exact merely by retuning it: change the number or order of scales, the source densities or source-set cardinalities, the nearest-source capacities, or a scalar-output stopping rule, while continuing to call the same estimator on fresh exchangeable samples. We show that this black-box route has a near-linear retained-source workload barrier on a simple family of graphs. The workload statement is the conceptual result of the paper. A round lower bound is derived only as a corollary for the standard sequential packetized implementation of the estimator. Neither statement is a lower bound for unrestricted exact girth in CONGEST, and neither contradicts the approximation theorem of Chechik et al. [3] Our hard instances are intentionally transparent. For an integer t ≥ 1, take an odd cycle of length gt = 8t + 1 and attach a complete binary tree of 2t − 1 vertices to every cycle vertex. The resulting

2 of 14

graph Ht has maximum degree three, a unique cycle, nt = (8t + 1)2t vertices, and diameter O(log nt ). For a source s, the BFS tree has exactly one non-parent cycle edge: the edge antipodal to the cycle vertex at which the source’s attached tree meets the cycle. If s lies δ edges away from the cycle, the corresponding estimator candidate is exactly gt + 2δ. Thus the exact value gt can be certified by this estimator only through a source on the unique cycle. The obstruction is rank rather than distance. At either antipodal endpoint needed by such a cycle source, a linear number of graph vertices are strictly closer than the source. A permutation-rank argument therefore bounds the usefulness of an exchangeable sample by the number of source records that survive nearest-source truncation. The argument is conditional, so it survives adaptive choices of later capacities and sample sizes and also a random stopping time. The main contributions are as follows. •

•

•

We formalize a black-box exactification class consisting of sequential calls to the nearest-source estimator on fresh exchangeable source sets. The source-set cardinality and table capacity may be chosen adaptively from previous scalar outputs, and the algorithm may stop at an adaptive stopping time. We prove a closure proposition showing that retuning the multi-scale template solely through its scale count/order, Bernoulli or fixed-cardinality source densities, capacities, and scalar-output stopping decisions falls in this class. We construct the bounded-degree, logarithmic-diameter family Ht and prove an exact witness characterization: on Ht , a call outputs the true girth only if a sampled cycle vertex is retained at both endpoints of its antipodal edge. Let T be the number of estimator calls, Q j the sampled-source cardinality, k j the nearest-source capacity, and Bj = min{ Q j , k j }. For every black-box exactification with finite expected workload, " # T 3gt Pr[A( Ht ) = gt ] ≤ E ∑ Bj . nt j =1

•

Hence constant exactness probability requires expected retained-source workload Ω(nt /gt ), which is Ω(nt / log nt ) on this family. For the standard sequential packetized implementation used to realize the estimator, a call with workload Bj serializes Θ( Bj ) retained records on every edge. The workload theorem therefore yields an implementation-specific corollary of Ω(nt / log nt ) expected rounds for constant exactness probability.

For context rather than as a second principal contribution, we also record the elementary sourcehitting observation that a known promise g ≥ h permits exact girth with constant probability using O(n/h) uniformly sampled complete source trees. This explains why an n/g source scale naturally appears without enlarging the scope of the lower bound. The result should be read as a separation between a successful approximation paradigm and its direct black-box exactification. It identifies what a stronger exact algorithm must change: exploit graph structure before sampling, preserve richer information than scalar estimator outputs and independent nearest-source tables, share state or compression across calls, or use a different exact-cycle certificate.

2. Materials and Methods 2.1. Model, Prior Work, and the Estimation Primitive 2.1.1. CONGEST and girth We consider a simple, connected, undirected, unweighted graph G = (V, E) with n = |V | and hop diameter D. Computation proceeds in synchronous rounds. In each round, each endpoint of an edge may send an O(log n)-bit message to the other endpoint. Vertices have unique O(log n)-bit identifiers. Local computation is free. This is the standard CONGEST model [4].

3 of 14

Notation conventions. For vertices u, v ∈ V, dG (u, v) denotes their shortest-path distance in G; when the ambient graph is clear we write d(u, v). For a connected subgraph H, d H (u, v) denotes distance restricted to H. We write ∆( G ) for maximum degree. The girth g( G ) is the length of a shortest simple cycle, with e (·) and Ω e (·) g( G ) = ∞ if G is acyclic; when the graph is clear we abbreviate this to g. The notation O suppresses factors polylogarithmic in n. Unless a probability exponent is displayed explicitly, “with high probability” means probability at least 1 − n−c0 for some fixed constant c0 > 0. Peleg, Roditty, and Tal gave foundational distributed algorithms for network diameter and girth [1]. Censor-Hillel et al. later obtained the first parameterized exact-girth algorithm in CONGEST, with complexity   e min{ g n1−1/Θ( g) , n} , O and polynomial improvements for several fixed even-cycle detection problems [2]. Manoharan and Ramachandran developed improved approximation algorithms for minimum-weight cycle in CONGEST [5]. Most recently, Chechik, Lifshitz, and Mukhtar obtained an f -approximation for e (n1/ f + D ) rounds for every constant integer f > 2 [3]. unweighted undirected girth in O On the lower-bound side, Frischknecht, Holzer, and Wattenhofer proved, for every fixed ε > 0, √ e ( n) lower bound for obtaining a (2 − ε)-approximation of unweighted girth in CONGEST, aΩ which in particular applies to exact computation [6]. Thus the unrestricted classical exact complexity √ remains separated between a near- n lower bound and a linear upper bound. Lower bounds for fixed-subgraph and cycle detection provide a complementary line of work [7,8]; Censor-Hillel et al. also identified a barrier to polynomially strengthening a known C6 -freeness lower bound using existing reduction technology [2]. Our result is of a different type: it proves a near-linear lower bound only for a specified exactification paradigm, rather than for arbitrary CONGEST algorithms. Table 1. The unrestricted exact-girth question and the restricted barrier proved here are different statements. The first row summarizes general CONGEST bounds; the next two rows summarize this paper’s model-specific consequences. Setting Unrestricted exact girth in CONGEST This paper: black-box estimator composition Standard packetized realization of that composition

Bound summarized here √ e ( n) lower bound inherited from (2 − Ω ε)-approximation; O(n) general upper bound Constant exactness requires E[W ] = Ω(nt /gt ), hence Ω(nt / log nt ) on Ht

E[ R] = Ω(nt / log nt ) on Ht

Scope Arbitrary CONGEST algorithms [1, 6] Retained-source workload; independent of how each estimator call is internally implemented Corollary for sequential unmodified estimator calls that explicitly exchange retained records

2.1.2. Nearest-source detection For a source set S ⊆ V and an integer k ≥ 1, let U (S, k, v) denote the min{k, |S|} closest sources to v, breaking distance ties by source identifier. Source detection constructs these ordered nearest-source records together with exact distances and shortest-path parent pointers. Lenzen and Peleg showed how to perform the corresponding source-detection task in essentially optimal O(k + D ) time in the relevant unbounded-depth setting [9]. The recent girth-approximation algorithm uses precisely this primitive [3]. We say that a source s is retained at v when s ∈ U (S, k, v). For every retained source, write d(s, v) for the exact graph distance and p(s, v) for the parent of v in the selected shortest-path tree rooted at s. When shortest paths are unique, p(s, v) is forced.

4 of 14

2.1.3. The estimator We use the deterministic procedure E STIMATE ( G, S, k ) introduced explicitly by Chechik et al. [3]. We paraphrase the operation because the exact details matter for the barrier. First, every vertex computes its nearest-source table U (S, k, v), distances, and parent pointers. Each vertex then sends its complete retained table to every neighbor. For an edge { x, y} and a source s appearing in both endpoint tables, the edge is a witness for s when neither endpoint is the other’s parent in the s-rooted shortest-path tree. Such a witness contributes the value d(s, x ) + d(s, y) + 1.

(1)

The global output is the minimum witness value, if no witness exists, we take the output to be +∞. Chechik et al. prove that this output is never below the true girth and, if a shortest cycle is covered by one retained source tree, obtain the additive guarantee used in their approximation analysis [3]. A source record consists of O(1) identifiers and an O(log n)-bit distance, and hence occupies O(log n) bits up to a constant factor. If |S| = Q, the table sent by every vertex contains exactly b(S, k ) = min{ Q, k }

(2)

records. In the standard packetized realization, the table-exchange stage explicitly serializes these b(S, k ) retained records on every directed edge and therefore takes Θ(b(S, k )) rounds up to implementation constants. This observation is used only for Corollary 2, the main workload theorem does not depend on a packet schedule. 2.2. Black-Box Exactification Model We isolate the direct strategy of retuning and repeatedly invoking the same nearest-source estimator. The definition below distinguishes the information visible to the black-box controller from the fresh source identities and internal nearest-source tables hidden inside each estimator call. This makes the adaptive stopping argument measure-theoretically explicit. Definition 1 (Fresh exchangeable nearest-source call). Fix G and let G be the information σ-field available immediately before a source set is sampled. Let the source cardinality Q ∈ {0, . . . , n} and capacity k ≥ 1 be G measurable. A fresh exchangeable nearest-source call samples S so that, conditional on G , S is uniform among all Q-subsets of V, and returns only the scalar value E STIMATE ( G, S, k ). Equivalently, after conditioning on all pre-sampling information and on the realized cardinality, the source-set distribution is invariant under every permutation of the vertex names. Independent Bernoulli sampling is included because, conditional on its realized cardinality, the selected set is uniform. Definition 2 (Black-box exactification with adaptive stopping). A black-box exactification is defined on a probability space with an algorithm-visible transcript filtration (F j ) j≥0 . The σ-field F j contains everything exposed to the controller after the first j completed estimator calls: previous controller-visible randomness, all previously chosen parameters, and the scalar outputs M1 , . . . , M j . It explicitly excludes the identities of the fresh samples and the internal nearest-source tables of completed calls. Before call j ≥ 1, the controller decides from F j−1 whether to stop. If it continues, it may reveal additional pre-sampling randomness and choose a cardinality Q j and capacity k j . Let G j ⊇ F j−1 be the resulting presampling σ-field. The continuation event and the values Q j , k j are G j -measurable. Conditional on G j , a fresh uniform Q j -subset S j is drawn and the call computes M j = E STIMATE ( G, S j , k j ). Only the scalar M j is added to the next controller-visible transcript F j , the sample identities and source tables are discarded from the black-box interface. The algorithm then repeats or stops. Let T ≥ 1 be the number of executed calls. By construction, T is a stopping time with respect to (F j ) j≥0 , and the returned value is min1≤ j≤T M j .

5 of 14

For an executed call define Bj = min{ Q j , k j },

(3)

and define the total retained-source workload T

W = ∑ Bj .

(4)

j =1

We restrict attention to algorithms with T < ∞ almost surely and E[W ] < ∞, otherwise the workload lower bound is vacuous. The information flow for an executed call is therefore

F j−1 −→ stop/continue and ( Q j , k j ) −→ G j −→ S j −→ M j −→ F j . In particular, k j cannot be correlated with the identities in S j through randomness revealed only after the source set is drawn. Later parameter choices may nevertheless depend arbitrarily on all earlier scalar outputs. controller transcript F j −1

choose Qj , k j

G j fixed

fresh sample Sj | Gj

E STIMATE ( G, S j , k j )

scalar Mj

continue: only M j is exposed Excluded from the black-box class: graph-aware source selection or preprocessing; persistence of source tables; joint compression across calls, auxiliary exact-cycle routines.

Figure 1. Information flow in the adaptive black-box exactification model. The controller may adapt Q j , k j , and the stopping decision to previous scalar outputs, but each source set is fresh and exchangeable conditional on the complete pre-sampling information G j , and internal nearest-source tables are not exposed to later calls.

Figure 1 emphasizes the interface restriction used by the theorem: source identities and nearestsource tables affect the scalar M j inside a call but are not available to the controller when choosing a later call. Proposition 1 (Closure under direct retuning of the multi-scale template). Consider an algorithm obtained from the unweighted undirected multi-scale nearest-source template of Chechik et al. [3] solely by changing any combination of: (i) the number or order of estimator calls, (ii) per-call independent Bernoulli sampling probabilities or fixed uniform source-set cardinalities, (iii) per-call nearest-source capacities, and (iv) future parameters and a continuation/stopping decision as functions of previous scalar estimator outputs. If calls use fresh samples, do not preserve or jointly compress their internal source tables, invoke no additional graphaware cycle routine, and return the minimum scalar estimate seen, then the resulting algorithm is a black-box exactification in the sense of Definition 2. Proof. A fixed-cardinality source set is uniform by assumption. For independent Bernoulli sampling, conditioning on its realized cardinality Q j makes every Q j -subset equally likely. Thus each call satisfies Definition 1 conditional on the complete pre-sampling state. Changes to scale order, sampling density, and capacity are precisely choices of ( Q j , k j ) made before the fresh sample is revealed. Dependence on earlier scalar outputs is allowed through F j−1 , and a scalar-output stopping rule makes T a stopping time with respect to the controller-visible filtration. The remaining hypotheses are exactly the state-discard and output restrictions in Definition 2. Proposition 1 is the model-naturalness claim used in this paper. The class is still deliberately restricted. It excludes graph-aware source selection or preprocessing, retention or combination of source-table state across calls, joint compression of several calls, and any additional exact-cycle

6 of 14

subroutine. Section 4 treats these exclusions as substantive escape routes rather than implementation details. 2.3. Notation Summary Table 2 collects the symbols used repeatedly in the model and the hard-family proof. Local proof variables are defined where they first appear. Table 2. Frequently used notation. Symbol

Meaning

G = (V, E); n; D dG (u, v); d H (u, v) g ( G ); ∆ ( G ) S; Q = |S|; k U (S, k, v) p(s, v) Mj ; Q j ; k j Bj = min{ Q j , k j } T; W = ∑ Tj=1 Bj Fj ; Gj

input graph; number of vertices; hop diameter shortest-path distance in G; distance restricted to a connected subgraph H girth; maximum degree source set; source-set cardinality; nearest-source capacity the min{k, |S|} closest sources retained at vertex v parent of v in the selected shortest-path tree rooted at source s scalar output, source cardinality, and capacity of estimator call j retained-source workload of call j adaptive stopping time; total retained-source workload controller-visible transcript after call j; information available immediately before sampling in call j hard graph; its unique cycle; its order; its girth cycle attachment of s; distance d(s, a(s)) from s to the cycle antipodal radius; antipodal edge; guaranteed number of strictly closer competitors number of rounds in the standard sequential packetized realization

Ht ; Ct ; nt ; gt a ( s ); δ ( s ) r; ei ; Nt R

2.4. Reproducibility The mathematical argument was developed by explicit theorem decomposition and adversarial checking of each quantifier: the hard graph is deterministic, all shortest paths are unique, the sampling bound is conditional on the realized source-set cardinality, and the final probability estimate uses only a union bound, so independence across layers is unnecessary. The supplementary verification program constructs finite instances directly from the definition and checks the structural identities used in the proof. No simulation is used to infer or fit an asymptotic exponent.

3. Results 3.1. The Hard Family For an integer t ≥ 1, let gt = 8t + 1. Start with a cycle Ct = (c0 , c1 , . . . , c gt −1 ) whose indices are taken modulo gt . At each cycle vertex ci , attach a complete rooted binary tree with 2t − 1 new vertices by connecting ci to the root. The root-to-leaf depth inside the attached tree is t − 1, so every attached-tree vertex is at graph distance at most t from its cycle attachment vertex. Denote the resulting graph by Ht . Figure 2 illustrates both the construction and the metric crowding at the antipodal endpoint that drives the lower bound.

7 of 14

(b) Antipodal crowding, shown for t = 2

(a) Hard-family geometry

s = ci

s = ci

x = ci+4t

ei

d( x, s) = 4t; highlighted anchors satisfy dCt ( x, c j ) ≤ 2t − 1. Thus Nt = (4t − 1)2t ≥ nt /3 vertices are strictly closer to x than s.

Figure 2. Geometry behind the barrier. (a) A schematic member of the cycle-of-binary-trees family, the actual cycle length is gt = 8t + 1. For a cycle source s = ci , the unique non-parent cycle edge is the antipodal edge ei . (b) The crowding argument, illustrated at t = 2 only for visual clarity. Around an antipodal endpoint x, the 4t − 1 highlighted anchor-plus-tree clusters contain Nt = (4t − 1)2t vertices that are all strictly closer to x than the exact-certifying source s.

Lemma 1 (Basic properties). For every t ≥ 1, the graph Ht satisfies nt = (8t + 1)2t ,

∆( Ht ) ≤ 3,

g( Ht ) = 8t + 1,

and D ( Ht ) = 6t. In particular, g( Ht ) = Θ(log nt ) and D ( Ht ) = Θ(log nt ). Proof. Each of the gt cycle vertices contributes itself together with 2t − 1 new tree vertices, hence nt = gt 2t . A cycle vertex has two cycle neighbors and one attached-tree neighbor. A tree vertex has degree at most three. Because every added component is a tree attached by a single edge, Ct is the unique cycle, and therefore the girth is gt . A vertex is at distance at most t from its attachment vertex. The distance between any two cycle vertices is at most ⌊ gt /2⌋ = 4t. Thus every pair of vertices is at distance at most t + 4t + t = 6t. Conversely, choose leaves at depth t − 1 in two attached trees whose cycle anchors are at cycle distance 4t. Each chosen leaf is at graph distance exactly t from its anchor, and the attached trees cannot shortcut the cycle, so the two leaves are at distance t + 4t + t = 6t. Hence D ( Ht ) = 6t. Finally, log2 nt = t + log2 (8t + 1), so t = Θ(log nt ), and the last two claims follow. 3.2. Exact Witnesses on the Hard Family The odd cycle makes all shortest paths in Ht unique. This removes parent-pointer ambiguity and allows an exact characterization of every candidate produced by a complete source tree. For a vertex s, let a(s) = ci be the unique cycle vertex at which the component containing s attaches to the cycle, taking a(s) = s when s ∈ Ct . Define δ(s) = d(s, a(s)). Let r = 4t = ( gt − 1)/2. For a(s) = ci , define the antipodal edge ei = { c i +r , c i +r +1 } . Both endpoints of ei are at cycle distance r from ci .

8 of 14

Lemma 2 (Unique witness edge). Fix a source s ∈ V ( Ht ) with a(s) = ci . In the complete BFS tree rooted at s, every edge of Ht except ei is a parent-child edge. The edge ei is not a parent-child edge, and its witness value is d(s, ci+r ) + d(s, ci+r+1 ) + 1 = gt + 2δ(s).

(5)

Proof. Every edge belonging to an attached binary tree is a bridge of Ht . Hence, for any root s, the unique shortest path to the farther endpoint of such an edge contains the edge, making the nearer endpoint its BFS parent. It remains to consider the cycle. Since gt = 2r + 1 is odd, between ci and any cycle vertex there is a unique shorter arc. For every cycle edge other than ei , the distances of its endpoints from ci differ by one, and the closer endpoint is the predecessor of the farther endpoint along its unique shortest path from ci . Prefixing the unique path from s to ci shows that the same parent-child relation holds in the BFS tree rooted at s. The endpoints of ei are both at distance r from ci , hence both at distance δ(s) + r from s. Neither can be the other’s parent. Substituting these distances into Equation (1) yields 2(δ(s) + r ) + 1 = 2δ(s) + (2r + 1) = gt + 2δ(s).

The same conclusion applies to a partial nearest-source table whenever s is retained at both endpoints of an edge: source detection reports exact distances and the same forced parent pointers. Corollary 1 (Exactness requires a cycle source). A call E STIMATE ( Ht , S, k ) outputs gt only if there exists a cycle vertex s = ci ∈ S that is retained at both endpoints of its antipodal edge ei . Conversely, if such a cycle source is retained at both antipodal endpoints, the call outputs gt . Proof. By Lemma 2, a retained source s can contribute only the candidate gt + 2δ(s). This equals gt exactly when δ(s) = 0, namely when s lies on the cycle. If a cycle source is retained at both endpoints of ei , that edge contributes gt . Since the estimator never outputs a value below the girth [3], the global minimum is exactly gt . 3.3. Antipodal Crowding and the Rank Bound The exact source characterized above is hard to retain. The reason is not that its antipodal endpoint is far away in an absolute sense: all relevant distances are only O(log nt ). The reason is that a linear number of vertices have smaller distance to that endpoint. In this subsection, dCt (u, v) denotes shortest-path distance measured along the cycle Ct . Lemma 3 (Linear antipodal crowding). Let s = ci be a cycle vertex and let x = ci+4t be one endpoint of its antipodal edge. At least Nt = (4t − 1)2t vertices of Ht are strictly closer to x than s is. In particular, Nt ≥

nt . 3

The same statement holds for the other antipodal endpoint. Proof. We have d( x, s) = 4t. Consider every cycle anchor c j satisfying dCt ( x, c j ) ≤ 2t − 1.

(6)

9 of 14

There are exactly 4t − 1 such anchors. Consider the anchor-plus-tree cluster consisting of an anchor together with all vertices of its attached binary tree. Every vertex v in any such cluster satisfies d( x, v) ≤ (2t − 1) + t = 3t − 1 < 4t = d( x, s). The 4t − 1 corresponding anchor-plus-tree clusters are disjoint and each has 2t vertices, proving the first claim. Moreover, Nt 4t − 1 1 = ≥ nt 8t + 1 3 for every t ≥ 1. Symmetry gives the second endpoint. We now isolate the elementary sampling fact that drives the barrier. Lemma 4 (Uniform-subset rank bound). Let z be a distinguished vertex and suppose a set A of N other vertices is strictly closer than z to some vertex x. Let S be a uniformly random Q-subset of an n-vertex ground set. For any k ≥ 1,   k Q . Pr[z ∈ S and z is among the k closest members of S to x ] ≤ min , n N+1

(7)

Proof. The first bound is immediate from Pr[z ∈ S] = Q/n. For the second, generate the uniform Q-subset by taking the first Q positions of a uniformly random permutation of all n vertices. Restrict this permutation to the N + 1 vertices A ∪ {z}. The relative rank of z in this restricted permutation is uniform on {1, . . . , N + 1}. If z ∈ S and at most k − 1 vertices strictly closer to x are selected before the cutoff, then at most k − 1 members of A can occur before z in the full permutation: every member of A preceding z is also selected because z itself appears among the first Q positions. Thus the event in Equation (7) implies that the relative rank of z inside A ∪ {z} is at most k. This occurs with probability at most k/( N + 1). The argument also covers Bernoulli sampling. Conditional on the random sample cardinality Q, a Bernoulli sample is uniform among all Q-subsets. More generally, it covers every exchangeable source-set distribution, which is a mixture of uniform fixed-cardinality samples. Lemma 5 (Per-call exactness). Consider a fresh exchangeable nearest-source call on Ht . Conditional on arbitrary values Q and k, let B = min{ Q, k }. Then   3gt B Pr[the layer outputs gt | Q, k ] ≤ min 1, . nt

(8)

Consequently, Pr[the layer outputs gt ] ≤

3gt E[ B]. nt

(9)

Proof. By Corollary 1, exactness requires at least one cycle source s = ci to be selected and retained at both endpoints of ei . It is necessary in particular that s be retained at one fixed antipodal endpoint x. By Lemma 3, at least Nt ≥ nt /3 vertices are strictly closer to x than s. Lemma 4 therefore gives   Q k 3 min{ Q, k } Pr[s selected and retained at x | Q, k ] ≤ min , ≤ . nt Nt + 1 nt A union bound over the gt possible cycle sources yields Equation (8). Taking expectation over Q and k yields Equation (9).

10 of 14

3.4. The Exactness Barrier We now lift the per-call bound to an adaptively stopped composition. Cross-call independence is not required. The only probabilistic restriction used below is the conditional exchangeability of the fresh source set after the algorithm has already chosen to execute the call and fixed its parameters. Theorem 1 (Adaptive retained-source workload barrier). Let A be a black-box exactification in the sense of Definition 2, with stopping time T and total retained-source workload W = ∑ Tj=1 Bj . On Ht , " # T 3gt 3gt Pr[A( Ht ) = gt ] ≤ E[W ] = E ∑ Bj . nt nt j =1

(10)

Consequently, success probability at least 2/3 requires

E[W ] ≥

2nt = Ω(nt /gt ) = Ω(nt / log nt ). 9gt

(11)

Proof. For j ≥ 1, let L j = { T ≥ j} be the event that call j is executed. Because the stopping decision is based on F j−1 , L j is F j−1 -measurable and hence G j -measurable. For bookkeeping, on Lcj set Bj = 0 and regard the event that call j outputs gt as false, extend G j arbitrarily there. Let Ej denote the event that call j is executed and its scalar output equals gt , and let 1 L j denote the indicator of L j . On L j , conditional on G j , the source set is a fresh uniform Q j -subset. Lemma 5 therefore gives Pr[ Ej | G j ] ≤ 1 L j

3gt Bj . nt

Because the estimator never returns a value below the true girth [3] and T < ∞ almost surely, the final minimum equals gt only if at least one event Ej occurs. Hence, by a countable union bound followed by conditional expectation and Tonelli’s theorem for nonnegative terms, Pr[A( Ht ) = gt ] ≤ ∑ Pr[ Ej ] j ≥1

  = ∑ E Pr[ Ej | G j ] j ≥1

3gt E[1 L j Bj ] nt j∑ ≥1 " # T 3gt = E ∑ Bj . nt j =1

≤

This proves Equation (10). Setting the left-hand side to at least 2/3 yields the explicit constant 2nt /(9gt ). Lemma 1 gives gt = Θ(log nt ). Theorem 1 is the principal result. It refers only to the amount of nearest-source state retained across the sequence of oracle-style estimator calls. It does not assume that the estimator is implemented by any particular packet schedule. Corollary 2 (Round barrier for the standard packetized realization). Suppose every estimator invocation is executed sequentially using the unmodified packetized realization described in Section 2.1.3, which explicitly sends the retained source records across each edge and does not reuse messages between calls. Let R be the total number of CONGEST rounds. Then, on Ht ,   gt E[ R] Pr[A( Ht ) = gt ] = O . nt

(12)

11 of 14

In particular, success probability at least 2/3 implies

E[ R] = Ω(nt /gt ) = Ω(nt / log nt ).

(13)

Thus no O(n1−ε ) exact-girth algorithm for all graphs, for fixed ε > 0, is obtained merely by executing such retuned black-box estimator calls in the standard sequential way. Proof. In an executed call j, every vertex retains Bj = min{ Q j , k j } source records. The standard estimator realization serializes these records in O(log nt )-bit CONGEST packets when exchanging the complete retained table with each neighbor. Consequently, there is an absolute constant c > 0 such that this table-exchange stage uses at least cBj rounds for each call. With sequential invocations and no cross-call message reuse, pathwise T

R ≥ c ∑ Bj = cW. j =1

Taking expectations and applying Theorem 1 proves Equation (12), the remaining claims follow from Equation (11) and gt = Θ(log nt ). Remark 1 (Scope of the round corollary). Corollary 2 is implementation-specific. The more fundamental statement is Theorem 1, which is a workload barrier inside the black-box model. Neither result applies to an arbitrary CONGEST algorithm that chooses sources from graph-dependent information, preserves and combines source tables across calls, jointly compresses several calls, computes additional cycle certificates, or abandons the nearest-source estimator. In particular, a simple graph-aware preprocessing step such as extracting the 2-core already defeats the specific obstruction on Ht . 3.5. Contextual Source-Hitting Observation The workload scale nt /gt has a simple source-hitting interpretation. The following observation is included only as context for that scale, it is not a second principal contribution. Proposition 2 (Contextual exact-girth bound under a girth promise). Suppose an undirected unweighted graph G has girth g ≥ h, where h ≥ 1 is known. There is a randomized CONGEST algorithm that computes the exact girth with probability at least 2/3 in O(n/h + D ) rounds up to absolute constants in the source-sampling probability. With high probability, exact girth can be computed in e (n/h + D ) O rounds. Proof. If G is acyclic, the exact answer is +∞, the proposition is relevant to the cyclic case, so assume g < ∞ and fix one shortest cycle C. For constant success probability, choose exactly q = min{n, ⌈cn/h⌉} sources uniformly without replacement, where c > 0 is a sufficiently large absolute constant. If q < n, then (n−q g)  g q Pr[S ∩ V (C ) = ∅] = n ≤ 1 − ≤ e−qg/n ≤ e−c . n (q) Choose c so that this probability is at most 1/3. The source count is deterministically q = O(n/h). Run complete source detection from every sampled source and retain all sampled sources. If s ∈ S ∩ V (C ),

12 of 14

the shortest cycle is covered by a source at distance zero, so the estimator returns exactly g [3]. Source detection and the table exchange use O(q + D ) = O(n/h + D ) rounds [9]. For high probability, choose instead q = min{n, ⌈cn log n/h⌉}. The same hypergeometric bound gives failure probability at most n−c , and the running time is e (n/h + D ). O For the family Ht , the constant-success form costs O(nt /gt + D ) = O(nt / log nt ) rounds, matching the nt /gt source-workload scale of Theorem 1 up to constant factors within this simple sourcehitting strategy. The high-probability form introduces the usual logarithmic amplification. 3.6. Finite-Instance Verification of the Structural Lemmas The results above are purely analytic. We nevertheless provide a small verification program as supplementary material to guard against implementation-level misunderstandings of the hard family. The program explicitly constructs Ht for t = 1, . . . , 6, runs BFS from every source for the witness check, and checks four statements independently of the proofs: (i) the graph has the claimed unique odd cycle and maximum degree, (ii) a deepest leaf has eccentricity 6t, confirming the stated diameter together with the analytic upper bound, (iii) every source has exactly one non-parent graph edge in its BFS tree and its candidate value is gt + 2δ(s), and (iv) every cycle source has at least nt /3 strictly closer competitors at each required antipodal endpoint. Table 3 reports the generated values. These checks are not evidence for the asymptotic theorem, they are reproducibility tests for the construction and the exact witness identity used in Lemmas 2 and 3. Table 3. Finite-instance verification generated by the supplementary script. The diameter column reports the verified value D ( Ht ) = 6t, the minimum crowding ratio is taken over all cycle sources and both antipodal endpoints.

t

nt

gt

D ( Ht )

1 2 3 4 5 6

18 68 200 528 1312 3136

9 17 25 33 41 49

6 12 18 24 30 36

minimum crowding ratio

witness identity

0.6667 0.7353 0.7500 0.7538 0.7546 0.7545

verified verified verified verified verified verified

4. Discussion and Scope 4.1. Why approximation survives The hard family does not contradict the approximation guarantee of Chechik et al. Their analysis does not require an exact cycle source to remain among the nearest sources at the antipodal edge. A source at distance δ > 0 can legitimately generate the value gt + 2δ, and multi-scale sampling controls this additive term sufficiently to obtain a multiplicative approximation. Our proof uses the much stricter equality condition gt + 2δ = gt , which forces δ = 0. The separation is therefore exactly between approximate coverage and exact certification. 4.2. Why the graph is not a diameter artifact A common failure mode in CONGEST lower-bound constructions is that a claimed communication obstruction is already explained by a large hop diameter. Here D ( Ht ) = O(log nt ). Moreover, the maximum degree is three and the unique cycle has logarithmic length. The obstruction is the nearest-source ranking at the antipodal edge: a linear-size metric ball lies strictly in front of the only sources that can certify equality.

13 of 14

4.3. Escape routes The theorem points toward several routes that are not covered by the barrier. First, a graph-aware algorithm might identify candidate cycle vertices or the 2-core and sample them with higher probability. On Ht , computing the 2-core immediately exposes the unique cycle, so the present family cannot support a lower bound against arbitrary preprocessing. This transparency is intentional: the purpose of Ht is to isolate a failure of the black-box estimator composition, not to hide the cycle from every distributed algorithm. Second, an algorithm might retain richer information than a bounded list of closest sources, for example compact sketches that preserve non-nearest cycle certificates. Third, several calls could share state or be jointly compressed, invalidating the additive workload interpretation. Fourth, an exact algorithm could combine source sampling with dedicated short-cycle detection or a decomposition theorem. These are not technical loopholes to be hidden, they are the principal boundary of the result. The contribution is the abstraction in Proposition 1 together with Theorem 1: the recent nearest-source approximation template cannot be made exact by scale/capacity retuning plus scalar-output adaptivity alone. We make no claim that exact girth itself intrinsically requires near-linear rounds. 4.4. Toward a stronger barrier A stronger negative result would replace the transparent cycle-of-trees family with graphs in which the shortest-cycle vertices are not locally distinguishable from a linear fraction of the graph, and would allow the algorithm to preserve state across phases. One possible target is an indistinguishability statement for algorithms whose only global metric information consists of k nearest-source labels per vertex, regardless of how those labels are scheduled. Such a theorem would move from a black-box barrier toward a genuine information restriction and would be of independent interest.

5. Conclusions Multi-scale nearest-source sampling is powerful enough to produce polynomially sublinear girth approximations, but direct black-box exactification imposes a qualitatively different certificate requirement. On the bounded-degree, logarithmic-diameter family Ht , the nearest-source estimator returns the true girth only when a cycle source survives at an antipodal edge despite a linear number of strictly closer competitors. Conditional exchangeability then gives an adaptive stopping-time bound Pr[A( Ht ) = gt ] ≤

3gt E[W ], nt

so constant exactness probability requires expected retained-source workload Ω(nt /gt ) = Ω(nt / log nt ). This workload theorem, rather than the packet-level implementation cost, is the central result. For the standard sequential packetized realization of the estimator, the workload barrier implies an Ω(nt / log nt ) expected-round corollary. That corollary is deliberately not advertised as a general CONGEST lower bound. The hard graph is transparent to graph-aware preprocessing, source tables are discarded between calls, and later decisions see only scalar estimator outputs. The result instead formalizes a precise paradigm separation: changing only source densities/cardinalities, nearest-source capacities, the order or number of scales, and scalar-output stopping decisions does not turn the recent multi-scale estimator into a polynomially sublinear exact algorithm. A stronger exact-girth result, positive or negative, must exploit information outside this closure. Supplementary Materials: The following supporting files accompany the manuscript: S1, verify_hard_family.py, which constructs the hard family and checks the finite witness and crowding identities, S2, verification_results.csv, the generated verification table.

Abbreviations

14 of 14

The following abbreviations are used in this manuscript: BFS breadth-first search CONGEST synchronous message-passing model with O(log n) bits per edge per round

References 1.

2.

3.

4. 5.

6.

7.

8.

9.

Peleg, D.; Roditty, L.; Tal, E. Distributed Algorithms for Network Diameter and Girth. In Proceedings of the Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012, Part II. Springer, 2012, Vol. 7392, Lecture Notes in Computer Science, pp. 660–672. https://doi.org/10.1007/978-3-642-31585-5_58. Censor-Hillel, K.; Fischer, O.; Gonen, T.; Le Gall, F.; Leitersdorf, D.; Oshman, R. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, Vol. 179, Leibniz International Proceedings in Informatics (LIPIcs), pp. 33:1–33:17. https://doi.org/10.4230/LIPIcs.DISC.2020.33. Chechik, S.; Lifshitz, G.; Mukhtar, D. Girth Approximations in the CONGEST Model. In Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC 2026). ACM, 2026, pp. 14–24. Preprint: arXiv:2603.27601. Peleg, D. Distributed Computing: A Locality-Sensitive Approach; SIAM: Philadelphia, PA, USA, 2000. https: //doi.org/10.1137/1.9780898719772. Manoharan, V.; Ramachandran, V. Computing Minimum Weight Cycle in the CONGEST Model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024). ACM, 2024, pp. 182–193. Preprint title: Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model, arXiv:2308.08670, https://doi.org/10.1145/3662158.3662801. Frischknecht, S.; Holzer, S.; Wattenhofer, R. Networks Cannot Compute Their Diameter in Sublinear Time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). SIAM, 2012, pp. 1150–1162. https://doi.org/10.1137/1.9781611973099.91. Gonen, T.; Oshman, R. Lower Bounds for Subgraph Detection in the CONGEST Model. In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018, Vol. 95, Leibniz International Proceedings in Informatics (LIPIcs), pp. 6:1–6:16. https://doi.org/10.4230/LIPIcs.OPODIS.2017.6. Le Gall, F.; Miyamoto, M. Lower Bounds for Induced Cycle Detection in Distributed Computing. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, Vol. 212, Leibniz International Proceedings in Informatics (LIPIcs), pp. 58:1–58:19. https://doi.org/10.4230/LIPIcs.ISAAC.2021.58. Lenzen, C.; Peleg, D. Efficient Distributed Source Detection with Limited Bandwidth. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2013, pp. 375–382. https://doi.org/10.1145/2484239.2484262.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Related documents

• Impact of quantified knee positioning on the measurement of minimal joint space width using statistical shape models: A cross-sectional and longitudinal analysis in the IMI-APPROACH.#255319
• Single Cutting Guides System for the Installation of a Total Knee Replacement#981639
• Rational acquisition of laboratory equipment: an accurate mathematical model to estimate the trade-offs in shared and nonshared equipment.#251093
• Application of Radiostereometric Analysis (RSA) to Triathlon Knee Components Inserted Using the OtisMed Custom-fit Total Knee Replacement System#801588
• A practical workflow for analyzing organelle spatial proximity with super-resolution microscopy.#785696