Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors establish tight existential bounds and computational complexity limits for the temporal exploration problem on directed dynamic graphs across various connectivity regimes. While exploration in undirected temporal graphs is relatively well-behaved, directed temporal snapshots impose severe structural bottlenecks, forcing a sharp quadratic lower bound even under maximum degree constraints of two or three. Key results prove that a lifetime of $\Theta(n^2)$ is necessary and sufficient for always-unilateral digraphs, show a tight $4n/3 - 1$ lifetime for semicomplete snapshots, and establish an optimal factor-$4/3$ approximation threshold that cannot be improved unless P$=$NP.
Directed temporal graphs demand $\Omega(n^2)$ exploration steps even when snapshot degrees are restricted to two, establishing an unavoidable quadratic barrier alongside a tight 4/3-approximation threshold.
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.