Pith Number

pith:6JGNKMT4

pith:2026:6JGNKMT4JUBAEAXC545J57CXOF

not attested not anchored not stored refs resolved

Semi-Synchronous Exploration in Dynamic Graphs

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

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

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

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{6JGNKMT4JUBAEAXC545J57CXOF}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We show that exploration is impossible if the adversary can deactivate at least ceil(k/(n-2)) - 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 ceil(k/(n-2)) - 2 agents per round.

C2weakest assumption

The underlying graph remains 1-interval connected in every round (connected despite arbitrary edge changes) with dynamic port labeling; the semi-synchronous adversary model and the specific visibility/communication capabilities are also load-bearing.

C3one line summary

Exploration of 1-interval connected dynamic graphs with k agents is impossible if an adversary deactivates at least ceil(k/(n-2))-1 agents per round and is achievable if at most ceil(k/(n-2))-2 are deactivated, requiring 1-hop visibility and communication.

References

19 extracted · 19 resolved · 0 Pith anchors

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

[2] Das, Graph exploration with mobile agents, in: Chapter 16 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, 2019, pp 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 2010

[4] 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 2012

[5] 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) (201 2014

Receipt and verification

First computed	2026-05-17T23:39:07.782269Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

f24cd5327c4d020202e2ef3a9efc57717c85b29c7cf371775392c9233c266950

Aliases

arxiv: 2605.14375 · arxiv_version: 2605.14375v1 · doi: 10.48550/arxiv.2605.14375 · pith_short_12: 6JGNKMT4JUBA · pith_short_16: 6JGNKMT4JUBAEAXC · pith_short_8: 6JGNKMT4

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/6JGNKMT4JUBAEAXC545J57CXOF \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: f24cd5327c4d020202e2ef3a9efc57717c85b29c7cf371775392c9233c266950

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "eedf9f5df596df31d1f6be0833a1c6522d4c3b6344841b6a9b428d6488a8f9ad",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.DC",
    "submitted_at": "2026-05-14T04:54:34Z",
    "title_canon_sha256": "e2e0b46acabef755a3ba73b1ac72021d96e30bfca06f24cd31dbfea30df69e9d"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.14375",
    "kind": "arxiv",
    "version": 1
  }
}