Bounds and algorithms for exploring time-changing directed networks
The directed temporal exploration problem
Data Structures and Algorithms
Summary
This paper studies how to explore networks where connections change over time and have directions. The authors find tight mathematical bounds on how long it takes to fully explore such networks under different connectivity conditions. They also provide an efficient algorithm to decide if exploration is possible within a given timeframe for certain types of networks. Additionally, they show that improving this decision process beyond a certain threshold is computationally very hard. These findings can help understand and work with time-dependent systems like communication or transportation networks.
What this means in practice
- •For network schedulers: Decide efficiently if a time-varying directed network can be fully explored within a certain time under semicomplete conditions.
- •For communication system designers: Understand minimum time bounds for guaranteed message delivery or coverage in changing directed communication networks.
A theory result. No direct application yet.
Authors
Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang, Hehui Wu
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.