2026-09-08T02:22:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26254 2026-09-05T19:39:35Z ddc:004 open_access

Brief Announcement: Exploration of Always S-Connected Temporal Graphs Adamson, Duncan Spirakis, Paul G Temporal Graphs Graph Exploration Treewidth Temporal graphs are a generalisation of (static) graphs, defined by a sequence of snapshots, each a static graph defined over a common set of vertices. Exploration problems are one of the most fundamental and most heavily studied problems on temporal graphs, asking if a set of m agents can visit every vertex in the graph, with each agent only allowed to traverse a single edge per snapshot. In this paper, we introduce and study always S-connected temporal graphs, a generalisation of always-connected temporal graphs where, rather than forming a single connected component in each snapshot, we have at most |S| components, each defined by the connection to at least one vertex in the set S. We use the model of always S-connected temporal graphs to study subgraphs of always-connected temporal graphs, with motivation coming from networks with a small number of "choke-points", such as rail networks, where all external traffic into a subnetwork comes from a limited number of external connections. We show that an always S-connected temporal graph with m = |S| and an average degree of Δ can be explored by m agents in O(n^{3/2} m³ Δ^{3/2} log^{3/2}(n)) snapshots, and, using this result as a subroutine, we show that any always-connected temporal graph with treewidth at most k can be explored by a single agent in O(n^{4/3} k^{11/2} log^{5/2}(n)) snapshots. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Duncan Adamson and Paul G Spirakis 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.20 urn:nbn:de:0030-drops-262542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode