CS Paper Radar

The directed temporal exploration problem

Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang, Hehui Wu

cs.DS math.CO ·submitted 2026-09-28 05:16 UTC · v2
theory

Abstract

We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of $O(n^2)$ suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a $Ω(n^2)$ lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for guaranteeing the existence of a temporal exploration on temporal digraphs where each snapshot is semicomplete. For always-strong temporal digraphs where each snapshot has minimum undirected degree at least $n - c - 1$, we prove that a lifetime of $O(cn)$ guarantees the existence of a temporal exploration, and we also prove that this is asymptotically tight. From a computational perspective, our results for temporal semicomplete digraphs also yield a polynomial-time, factor-$4/3$ algorithm for deciding if a temporal semicomplete digraph admits a temporal exploration within the first $\ell$ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - ε)$ approximation algorithm exists, even if every snapshot is a tournament, unless P$=$NP.

Closest papers

Nearest neighbours by meaning across the whole index.

Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs

cs.DS cs.DM ·2026-10-05 ·Daniele Carnevale
theory similarity 0.82
Abstract · 21 pages, 2 figures

A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time step wait or move along an edge of the current snapshot, and the temporal graph is explored once the agent has visited every vertex. We consider always-connected temporal graphs, in which every snapshot is connected, and ask how long exploration can be forced to take when the underlying graph, the union of all snapshots, has maximum degree at most~$Δ$. Two lower bounds were known in this setting, $Ω(Δn)$ and $Ω(n\log n)$, realised by different constructions. We establish a stronger lower bound, answering a question of Bastide, Groenland, Michel and Rambaud. Specifically, for every $n$ and $Δ$ with $Δ_0\leΔ\le n-1$ we construct an always-connected temporal graph on $n$ vertices with underlying maximum degree at most~$Δ$ that cannot be explored in fewer than $γ\,Δn\,(1+\log(n/Δ))$ time steps from any start vertex, where $γ>0$ and $Δ_0$ are absolute constants. The construction is deterministic, and every snapshot is a spanning tree with exactly one vertex of degree greater than three. Time is divided into phases. In each phase, a rotating-cycle gadget prevents the agent from reaching more than half of the trees attached to it. Between phases, we reassign target vertices among these trees using walks on a constant-degree expander, and a Gray code order of the targets keeps the underlying degree bounded. The reassignment guarantees that, for any walk of the agent, some target remains unvisited throughout all phases.

0.41

Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings

cs.DS cs.CCcs.DMmath.CO ·2026-10-21 ·Frank Kammer, Sandra Kiefer, Johannes Meintrup
top venuetheory similarity 0.68
Abstract · Full version of a paper accepted for publication at SODA 2027. 37 pages, 3 figures

Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with $n$ vertices can be explored in $O(qn\log^3(n))$ time steps, where $q$ is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small $q$, our bound substantially improves on the known worst-case bound of $Θ(n^2)$ in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of $Ω(n\log(n))$ when $q$ is constant and $Ω(qn)$ when $1 \leq q \leq n$. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in $O(n\log^3(n))$ time steps, leaving a gap of only $\log^2(n)$ to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an $O(rn^{1+ε})$ bound for TEXP, for every fixed $ε> 0$, where $r$ is the number of orbits, and an $O(n^{1+ε})$ bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on $n$ in the upper bounds on the number of time steps is decreased from $n^{1+ε}$ to $n\log^3(n)$ for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by $r$. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP.

0.42

Almost Linear 3-Spanners of Temporal Cliques

cs.DS cs.DMmath.CO ·2026-09-02 ·Julia Baligacs, Davide Bilò, Václav Blažej, Maël Dumas, Anna Zych-Pawlewicz
theory similarity 0.66
Abstract

Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $α$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $α$. While general temporal graphs may not admit sparse temporal $α$-spanners for any value of $α$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $Ω(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

0.36

Tight Hardness for Temporal Path Covers at Vertex-Cover Number Two

cs.DS ·2026-09-12 ·Alp Par
similarity 0.66
Abstract · 14 pages, 2 figures. Includes supplementary computational validation and strengthened tractability results for TDPC on temporal oriented sta…

Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TDPC) ask for minimum-cardinality covers of a temporal digraph by temporal paths, with TDPC additionally requiring pairwise temporal disjointness. Cioni et al. proved both problems NP-hard on temporal DAGs whose underlying undirected graph has vertex-cover number three and left the vertex-cover-two case open. We resolve this question affirmatively for both problems. Using polynomial-time reductions from Distinct Numerical Matching with Target Sums, we show that TPC and TDPC are NP-complete already when the underlying undirected graph has vertex-cover number exactly two. For TPC, this yields an exact vertex-cover threshold: polynomial-time solvability at vertex-cover number at most one and NP-completeness at two. For TDPC, we further study the boundary case of temporal oriented stars. A reuse-normalization argument reduces optimum solutions to leaf-unique two-edge merges. If either the incoming or outgoing side is single-label, the optimum remains polynomial-time computable even when the opposite side is multi-label. We also introduce a span parameter for feasible merge realizations and prove that any feasible family of k merges forces a realization of span at least 2k-2. Hence TDPC on temporal oriented stars is in XP parameterized by maximum span, and is polynomial-time solvable for every fixed span bound. The unrestricted multi-label star case remains open.

0.47

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

cs.DS ·2026-11-02 ·Prantar Ghosh, Amirhossein Janfaza
theory similarity 0.62
Abstract

We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining the number of semi-streaming passes needed to solve directed $s,t$-reachability: there is an exponential gap---$Ω(\log n/\log \log n)$ vs $n^{1/2+o(1)}$---between the best-known lower and upper bounds. Several related fundamental digraph problems, e.g., topological sorting, acyclicity testing, and decomposition into strongly connected components (SCCs), are known to have the same semi-streaming pass lower bound. However, no $o(n/\text{polylog}(n))$-pass upper bound was known for any of them. Our main result achieves an $n^{1/2+o(1)}$-pass semi-streaming algorithm for each of these problems. As a corollary, we get algorithms with the same pass and space usage for a broad class of DAG problems that admit a certain form of dynamic program over a topological ordering. This class includes weighted single-source shortest paths, longest paths, max-outdegree+1 coloring, and constructing a lexicographically-first DFS (depth-first search) forest. Our algorithm for the last problem can be seen as a generalization of our results on topological sorting and acyclicity testing: recall that standard textbook algorithms for these problems use DFS as a subroutine. Our algorithms are optimal up to an $n^{o(1)}$ factor in passes under the reasonable conjecture that $s,t$-reachability requires $Ω(\sqrt{n})$ semi-streaming passes. However, using the fact that our algorithms can be parameterized by the number of passes taken by topological sorting or single-source reachability algorithms, we prove stronger lower bounds for some of the problems even under weaker conjectures.

0.28

Deterministic Connectivity Sketches Under Edge Deletions

cs.DS ·2026-11-04 ·Sanjeev Khanna, Aaron Putterman, Madhu Sudan
theory similarity 0.62
Abstract

How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic streaming algorithms for graph connectivity. Towards answering this question, we study the deterministic one-way communication problem in which Alice holds a graph $G_A = (V, E_A)$ on $n$ vertices, Bob holds a graph $G_B = (V, E_B)$ with $E_B \subseteq E_A$, and Alice sends a message $M \in \{0,1\}^m$ that allows Bob to decide whether $G_A - G_B$ is connected. Randomized sketches solve this problem using $\tilde O(n)$ bits, whereas deterministic recovery of even one surviving edge requires $Ω(n^2)$ bits. We prove an upper bound of $m = \widetilde{O}(n^{7/4})$ bits and a lower bound of $m = \widetildeΩ(n^{3/2})$ bits for deciding connectivity. Thus, connectivity admits a subquadratic deterministic representation despite the quadratic cost of edge recovery, but remains polynomially harder than its randomized counterpart. The upper bound immediately yields an $\widetilde{O}(n^{7/4})$-bit deterministic $n^2$-fault tolerant connectivity oracle, which reports the connected components of a graph $G$ after any valid set of edge deletions. We also obtain an $\tilde Ω(n f^{1/4})$-bit lower bound for deterministic $f$-fault tolerant connectivity oracles for every $f \in [1,n^2]$. Finally, we show that the separation between connectivity and edge recovery persists in deterministic single-pass dynamic streams with bounded update multiplicity. For every fixed $ε\in (0,1/3)$, our algorithm reports the connected components of the final simple graph using $\widetilde{O}(n^{15/8 + 3ε/8})$ bits (subquadratic space), provided each edge undergoes at most $n^ε$ insertion or deletion updates in total.

0.25

Safe Exploration of Arbitrary Dynamic Dangerous Networks

cs.DC ·2026-09-17 ·Caterina Feletti, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
theory similarity 0.62
Abstract

Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes.

0.05

Parameterized Complexity of Temporal Agony

cs.DS ·2026-08-20 ·Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz
publishedhot direction similarity 0.62
Abstract · To appear at ALGOWIN 2026

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

0.37