arxiv: 2605.14375 · v1 · submitted 2026-05-14 · 💻 cs.DC

Recognition: no theorem link

Semi-Synchronous Exploration in Dynamic Graphs

Ashish Saxena , Anisur Rahaman Molla , Kaushik Mondal , Gokarna Sharma

Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:51 UTC · model grok-4.3

classification 💻 cs.DC

keywords dynamic graphsmobile agentsgraph explorationsemi-synchronous scheduleradversarial deactivation1-interval connectivityagent coordination

0 comments

The pith

Mobile agents cannot explore 1-interval connected dynamic graphs if an adversary deactivates ceil(k/(n-2)) - 1 or more agents per round.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes tight bounds for the exploration problem in 1-interval connected dynamic graphs under a semi-synchronous scheduler. It proves that with k agents on n nodes, if the adversary can deactivate at least ceil(k/(n-2)) - 1 agents per round, exploration is impossible even with unbounded memory, global communication, and full visibility. This implies exploration is only solvable when the adversary deactivates at most ceil(k/(n-2)) - 2 agents per round. The authors further show that 1-hop visibility and 1-hop communication are necessary to achieve the threshold, and provide a matching algorithm using k agents with 1-hop visibility and global communication.

Core claim

In 1-interval connected dynamic graphs with dynamic port labeling, under semi-synchronous execution where an adversary deactivates agents each round, exploration by k mobile agents is impossible whenever the adversary deactivates at least ceil(k/(n-2))-1 agents per round. This holds even with unbounded memory, global communication and full visibility. Consequently, exploration is solvable only if the adversary deactivates at most ceil(k/(n-2))-2 agents per round, and this requires agents to have 1-hop visibility and global communication.

What carries the argument

The threshold ceil(k/(n-2)) that bounds the number of allowable agent deactivations per round by the adversary in the semi-synchronous model for dynamic graph exploration.

If this is right

Exploration requires the number of agents k to scale with both n and the expected per-round deactivations the system must tolerate.
Agents need only 1-hop visibility plus global communication to match the upper bound on tolerable deactivations.
The impossibility result separates the minimal visibility and communication requirements from the deactivation threshold.
The bound is tight because the paper supplies both an impossibility proof and a matching algorithm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar deactivation thresholds may appear in other coordination tasks such as leader election or information dissemination on dynamic networks.
In applications like robot swarms, the ratio k/(n-2) indicates that substantially more agents than nodes are needed to withstand moderate adversarial failures.
The connectivity assumption (1-interval connected) is critical; relaxing it to weaker connectivity would likely lower the allowable deactivation count.

Load-bearing premise

The underlying graph remains connected in every round despite arbitrary edge changes, and the semi-synchronous scheduler lets the adversary choose deactivations up to the stated bound.

What would settle it

An explicit protocol that completes exploration when the adversary deactivates ceil(k/(n-2)) - 1 agents per round, or a counter-example showing failure with only ceil(k/(n-2)) - 2 deactivations.

Figures

Figures reproduced from arXiv: 2605.14375 by Anisur Rahaman Molla, Ashish Saxena, Gokarna Sharma, Kaushik Mondal.

**Figure 3.** Figure 3: The construction of Cr when EGr−1 (wn−1) ̸= 0. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: The pre-computation of agents in Cr. u1 u2 un−5 un−4 un−3 un−2 un−1 un α ′ 2 β ′ β 1 ′ 2 γ2 γ1 δ1 X3 X2 X1 Y [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

**Figure 6.** Figure 6: The construction of C ′ r when Y = 1. ∗ Case 1.3.2.4: Consider the following equations hold. X1 − α ′ 2 + β ′ 1 = 1 (57) X2 − (β ′ 1 + β ′ 2 ) + (α ′ 2 + γ1) = 1 (58) This case shows that agents are not in C ∗ form at the end of round r. As in C ∗ , there is exactly one node with one agent. Case 1.4: As per pre-computation in Cr, the following equations hold. X1 − (α1 + α2) + β1 = 1 (59) X2 − (β1 + β2) + (… view at source ↗

**Figure 7.** Figure 7: The construction of C ′ r when Y = 0. In this case, the value of γ ′ 2 = γ2 in C ′ r as the number of agents at node un−5 in Cr and C ′ r is p + 1; otherwise there will be two nodes with one agent in C ′ r . Therefore, using Eq. 63 and Eq. 82, we have β1 = p, which leads to a contradiction due to Eq. 79. → Case 2.2.2.2.2: Consider the following holds. X2 − (β1 + β2) + (α2 + γ1) = p + 1 (83) X3 − (γ1 + γ2) … view at source ↗

**Figure 8.** Figure 8: The construction of Cr when Y = 1. u1 u2 un−2 un−1 un Y λ2 λ1 [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗

read the original abstract

We study the fundamental problem of graph exploration in dynamic graphs using mobile agents. We consider $1$-interval connected dynamic graphs, where the topology may change arbitrarily from round to round as long as the graph remains connected, and edges are assigned with the dynamic port labeling at each round. The execution follows a semi-synchronous scheduler, under which an adversary may deactivate an arbitrary subset of agents in each round. For a graph with $n$ nodes and $k$ agents, we show that exploration is impossible if the adversary can deactivate at least $ \left\lceil \frac{k}{n-2} \right\rceil - 1$ agents per round, even when agents are equipped with unbounded memory, have global communication and full visibility. This yields an upper bound, implying that exploration is solvable only when the adversary deactivates at most $\left\lceil \frac{k}{n-2} \right\rceil - 2$ agents per round. We further establish that achieving exploration at this threshold requires agents to have both $1$-hop visibility and $1$-hop communication. Finally, we present the exploration algorithm using $k$ agents when the adversary deactivates at most $ \left\lceil \frac{k}{n-2} \right\rceil - 2$ agents, assuming agents are equipped with $1$-hop visibility and global communication, and matches the adversarial deactivation bound implied by the impossibility results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down a deactivation threshold for semi-synchronous agent exploration but the formula breaks for small k and needs an explicit precondition.

read the letter

The main point is that this work gives a precise bound on how many agents an adversary can knock out per round before exploration fails in 1-interval-connected dynamic graphs. With k agents and n nodes, the claim is that exploration is impossible once the adversary can deactivate at least ceil(k/(n-2)) - 1 agents each round, even with unbounded memory, global communication, and full visibility. That produces the matching statement that the problem is solvable only when deactivations stay at or below ceil(k/(n-2)) - 2, and that 1-hop visibility plus 1-hop communication are required to hit the bound. The abstract also supplies an algorithm that meets the threshold under those visibility assumptions and global communication. The counting argument over the n-2 nodes looks like the core of the impossibility direction, and the abstract states the claims without obvious internal contradictions. What the paper does cleanly is separate the necessity of limited visibility from the sufficiency of the deactivation bound. The soft spot is the lack of a precondition on k. When k is at most n-2 the expression ceil(k/(n-2)) - 1 evaluates to 0, so the impossibility result would say exploration fails even with zero deactivations. That cannot hold in a 1-interval-connected graph, where a single active agent can traverse the nodes round by round. The paper states the bound for arbitrary k without noting the range where it is meaningful, which makes the quantitative threshold the weakest part of the central claim. The algorithm section assumes the 1-hop capabilities to match the bound, but without the full proofs it is difficult to check the exact counting steps. This paper is aimed at people working on mobile agents and fault-tolerant exploration in dynamic networks. A reader who already knows the prior dynamic-graph literature will get value from the specific threshold and the visibility requirement, provided the small-k case is fixed. It deserves peer review because the impossibility direction is interesting and the matching algorithm is a concrete contribution, even though the presentation of the bound needs tightening to avoid the edge-case problem.

Referee Report

2 major / 2 minor

Summary. The manuscript studies exploration of 1-interval connected dynamic graphs by k mobile agents under a semi-synchronous adversary that may deactivate agents each round. It proves that exploration is impossible when the adversary can deactivate at least ⌈k/(n-2)⌉−1 agents per round (even with unbounded memory, global communication, and full visibility), and supplies a matching algorithm that succeeds when the adversary deactivates at most ⌈k/(n-2)⌉−2 agents, provided agents have 1-hop visibility and global communication.

Significance. If the quantitative thresholds are corrected, the work supplies tight, parameter-based bounds on tolerable deactivations for dynamic-graph exploration, clarifying the precise visibility and communication requirements needed to match the impossibility threshold.

major comments (2)

[Abstract] Abstract (and the central impossibility theorem): the stated threshold ⌈k/(n-2)⌉−1 evaluates to 0 for all k≤n-2, which would assert impossibility even under zero deactivations. This is inconsistent with 1-interval connectivity, under which a single agent can traverse the graph when no agents are deactivated. The theorem statement must either add an explicit precondition k> n-2 or revise the formula.
[Impossibility proof] Impossibility section (counting argument): the derivation that produces the ⌈k/(n-2)⌉ term must be checked against the case k≤n-2; if the argument silently assumes k>2(n-2), the assumption must appear in the theorem statement so that the bound does not collapse for small k.

minor comments (2)

[Abstract] Abstract: the sentence 'This yields an upper bound, implying that exploration is solvable only when…' is imprecise; the result is an upper bound on the number of tolerable deactivations.
[Algorithm] Algorithm section: confirm that the presented algorithm explicitly handles the boundary case k=n-1 (where the threshold becomes 1) and state the exact visibility/communication assumptions used in the pseudocode.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the inconsistency in the threshold for small k. We agree that the current formulation of the impossibility result is incorrect when k ≤ n-2 and will revise the manuscript to add the explicit precondition k > n-2 to the abstract, theorem statements, and proof. This change clarifies the result without affecting the core contributions for the parameter regimes where the bound is meaningful.

read point-by-point responses

Referee: [Abstract] Abstract (and the central impossibility theorem): the stated threshold ⌈k/(n-2)⌉−1 evaluates to 0 for all k≤n-2, which would assert impossibility even under zero deactivations. This is inconsistent with 1-interval connectivity, under which a single agent can traverse the graph when no agents are deactivated. The theorem statement must either add an explicit precondition k> n-2 or revise the formula.

Authors: We agree with the observation. The counting argument underlying the impossibility theorem implicitly requires k > n-2 for the ceiling expression to yield a positive deactivation threshold that forces impossibility. For k ≤ n-2 the result does not hold, as a single agent (or small team) can explore under zero deactivations. We will add the precondition k > n-2 to the abstract and the central theorem, and we will update the surrounding text to reflect this restriction. revision: yes
Referee: [Impossibility proof] Impossibility section (counting argument): the derivation that produces the ⌈k/(n-2)⌉ term must be checked against the case k≤n-2; if the argument silently assumes k>2(n-2), the assumption must appear in the theorem statement so that the bound does not collapse for small k.

Authors: We have re-examined the counting argument. It partitions the k agents into groups whose size is governed by n-2 (the number of non-root nodes that must be visited in the worst-case 1-interval-connected graph). The argument is valid precisely when k > n-2; it does not require the stronger assumption k > 2(n-2). We will insert the explicit precondition k > n-2 into the theorem statement and add a short clarifying paragraph at the beginning of the impossibility section explaining why the bound collapses for smaller k. revision: yes

Circularity Check

0 steps flagged

Derivation of deactivation thresholds and exploration algorithm is self-contained

full rationale

The paper establishes an impossibility result showing exploration fails if the adversary deactivates at least ceil(k/(n-2))-1 agents per round in 1-interval-connected graphs, then presents a matching algorithm solvable when at most ceil(k/(n-2))-2 are deactivated under 1-hop visibility and global communication. These thresholds are derived directly from the model parameters n and k via combinatorial arguments on agent coverage and connectivity, without any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The central claims rest on the stated assumptions of semi-synchronous scheduling and dynamic port labeling, which are external to the derived bounds. No step reduces the result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard dynamic-graph and mobile-agent model assumptions rather than new free parameters or invented entities.

axioms (2)

domain assumption The graph is 1-interval connected in every round
Invoked in the model definition and used throughout the impossibility and algorithm arguments.
domain assumption Dynamic port labeling at each round
Stated as part of the graph model; agents must handle changing labels.

pith-pipeline@v0.9.0 · 5564 in / 1281 out tokens · 55129 ms · 2026-05-15T01:51:18.157806+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

C. E. Shannon, Presentation of a maze-solving machine, Claude Elwood Shannon Collected Papers (1993) 681–687

work page 1993
[2]

Das, Graph exploration with mobile agents, in: Chapter 16 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, 2019, pp

S. Das, Graph exploration with mobile agents, in: Chapter 16 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, 2019, pp. 403–422

work page 2019
[3]

F. Kuhn, N. Lynch, R. Oshman, Distributed computation in dynamic networks, in: STOC’2010, Association for Computing Machinery, New York, NY, USA, p. 513–522

work page 2010
[4]

Casteigts, P

A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro, Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Sys- tems 27 (5) (2012) 387–408

work page 2012
[5]

Michail, I

O. Michail, I. Chatzigiannakis, P. G. Spirakis, Causality, influence, and computa- tion in possibly disconnected synchronous dynamic networks, Journal of Parallel and Distributed Computing 74 (1) (2014) 2016–2026

work page 2014
[6]

Saxena, K

A. Saxena, K. Mondal, Path connected dynamic graphs with a study of dispersion and exploration, Theoretical Computer Science 1050 (2025) 115390

work page 2025
[7]

Gotoh, Y

T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, T. Masuzawa, Group exploration of dynamic tori, in: ICDCS 2018, IEEE, 2018, pp. 775–785

work page 2018
[8]

Gotoh, Y

T. Gotoh, Y. Sudo, F. Ooshita, T. Masuzawa, Exploration of dynamic ring networks by a single agent with the h-hops and s-time steps view, in: SSS 2019, Springer, pp. 165–177

work page 2019
[9]

Gotoh, P

T. Gotoh, P. Flocchini, T. Masuzawa, N. Santoro, Exploration of dynamic networks: Tight bounds on the number of agents, Journal of Computer and System Sciences 122 (2021) 1–18

work page 2021
[10]

Di Luna, S

G. Di Luna, S. Dobrev, P. Flocchini, N. Santoro, Distributed exploration of dynamic rings, Distributed Computing 33 (2020) 41–67

work page 2020
[11]

Bournat, S

M. Bournat, S. Dubois, F. Petit, Computability of perpetual exploration in highly dynamic rings, in: ICDCS 2017, IEEE, 2017, pp. 794–804. 33

work page 2017
[12]

A. D. Kshemkalyani, A. R. Molla, G. Sharma, Efficient dispersion of mobile robots on dynamic graphs, in: ICDCS 2020, 2020, pp. 732–742

work page 2020
[13]

Saxena, K

A. Saxena, K. Mondal, Natural Calamities Demand More Rescuers: Exploring Con- nectivity Time Dynamic Graphs, in: DISC 2025, Vol. 356, 2025, pp. 41:1–41:23

work page 2025
[14]

S. Das, N. Giachoudis, F. L. Luccio, E. Markou, On the broadcast problem for mobile agents in dynamic networks, Discrete Applied Mathematics 379 (2026)

work page 2026
[15]

P.Flocchini, M.Kellett, P.C.Mason, N.Santoro, Searchingforblackholesinsubways, Theory of Computing Systems 50 (2012) 158–184

work page 2012
[16]

Flocchini, B

P. Flocchini, B. Mans, N. Santoro, On the exploration of time-varying networks, The- oretical Computer Science 469 (2013) 53–68

work page 2013
[17]

D.Ilcinkas, A.M.Wade, Onthepowerofwaitingwhenexploringpublictransportation systems, in: OPODIS 2011, Springer, 2011, pp. 451–464

work page 2011
[18]

Ilcinkas, A

D. Ilcinkas, A. M. Wade, Exploration of the t-interval-connected dynamic graphs: the case of the ring, Theory of Computing Systems 62 (2018) 1144–1160

work page 2018
[19]

Bournat, A

M. Bournat, A. K. Datta, S. Dubois, Self-stabilizing robots in highly dynamic envi- ronments, in: SSS 2016, Springer, 2016, pp. 54–69. 34

work page 2016