PaperlayerView exact revision on arXiv

Source-linked AI summary

The directed temporal exploration problem

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

arXiv:2609.34339v2cs.DSmath.CO

TL;DR

Temporal exploration asks whether a temporal digraph has a temporal walk spanning every vertex, and the paper studies sufficient conditions under snapshot connectivity requirements. Its proofs use probabilistic methods and travel plans; the results establish quadratic sufficiency and an O(cn) bound in a specified always-strong setting.

  • Problem

    Temporal exploration asks whether a temporal digraph admits a temporal walk spanning every vertex; the paper seeks sufficient conditions under snapshot connectivity requirements such as always-unilaterality.

    Source: §1 · p. 2

  • Method

    The proof of the always-strong bound uses the probabilistic method, particularly the Lovász Local Lemma, while travel plans guide walks that cover many vertices.

    Source: §1 · p. 4, §5.2 · p. 30

  • Results

    O(n^2) snapshots suffice for always-unilateral exploration, while a directed-path-snapshot example remains unexplorable at lifetime ≥1/128 n^2; always-strong D with ¯δ(D) ≤ c admit exploration in O(cn).

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    FastestTemporalExploration cannot be approximated within a factor (4/3 − ϵ), even on temporal tournaments, unless P = NP.

    Source: §1 · p. 4

    The corresponding undirected cases with ¯δ(G) ≥ n/2 remain open.

    Source: §1 · p. 4

Abstract

from arXiv · show

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 $\Omega(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 - \epsilon)$ approximation algorithm exists, even if every snapshot is a tournament, unless P$=$NP.

1 Introduction

The paper establishes lifetime bounds for temporal exploration under always-unilateral and dense-snapshot conditions, and gives matching lower bounds in several settings. It also develops a travel-plan proof strategy and derives algorithmic hardness results for temporal tournaments.

1 Introduction

  • Theorem 1 guarantees a walk spanning any prescribed k-vertex set in O(kn + k^2) snapshots, yielding an O(n^2) exploration bound when the set is all vertices.This answers affirmatively a question about improving the earlier bound for spanning a prescribed set.Source: §1 · pp. 2–3
  • O(n^2) snapshots suffice for always-unilateral temporal exploration, and a matching asymptotic lower bound holds even when every snapshot is a directed path.The lower-bound construction has underlying-union maximum degree at most 3.Source: §1 · p. 3
  • A lifetime of ⌊4n/3 − 1⌋ suffices for semicomplete temporal digraphs, while temporal tournaments can fail to be explorable at lifetime ⌊4n/3 − 2⌋.The sufficient bound is presented in Theorem 3 and the non-explorable example in Theorem 4.Source: §1 · p. 3
  • FastestTemporalExploration cannot be approximated within 4/3 − ε on temporal tournaments unless P = NP.TemporalExploration is also NP-hard on temporal tournaments with lifetime n − 1.Source: §1 · pp. 3–4
  • The authors leave open whether the large-minimum-degree upper bound extends to always-unilateral digraphs, and note unresolved undirected cases when the complement degree is at least n/2.They also report no known counterparts of the corresponding large-minimum-degree bounds for undirected temporal graphs.Source: §1 · p. 4
  • For always-strong temporal digraphs with complement minimum degree at most c, O(cn) snapshots suffice, and a construction gives a matching asymptotic lower bound.The lower-bound lifetime is c(n − c − 2).Source: §1 · p. 4
  • The proof for large minimum degree uses the Lovász Local Lemma and travel plans to separate vertex ordering from finding vertices that reach many unexplored vertices.The authors suggest that the travel-plan framework may extend to other settings reducible to finding many travel plans.Source: §1 · p. 4

2 Preliminaries

The preliminaries establish the notation for digraphs and temporal digraphs, define connectivity and temporal exploration, and introduce reachability and walk operations used in the paper.

Digraphs

  • A digraph is semicomplete when its underlying graph is complete, while a tournament has exactly one arc between each vertex pair.Source: §2 · p. 5

Temporal digraphs

  • A temporal digraph is a sequence of snapshots on a shared vertex set; its lifetime is the number of snapshots, and its underlying graph is the union of their underlying graphs.Source: §2 · p. 5

Connectivity

  • A temporal digraph is always-unilateral if every snapshot is unilateral and always-strong if every snapshot is strongly connected; always-strong implies always-unilateral.Source: §2 · p. 5

Temporal walks

  • A temporal walk follows arcs in strictly increasing snapshot order, and a temporal exploration is a temporal walk spanning every vertex.Source: §2 · p. 5

Reachability

  • The notation distinguishes temporal reachability from reachability within an initial segment of snapshots, and defines concatenation for temporal walks.Source: §2 · pp. 5–6

3 Temporal exploration problem

This section studies temporal exploration in always-unilateral temporal digraphs, establishing lifetime sufficiency guarantees alongside quadratic-lifetime obstructions in bounded-degree settings. It also develops reachability bounds supporting these exploration results.

3.1 Always-unilateral temporal digraphs

  • ℓ(D) ≥ (n-1)^2 suffices for exploration in always-strong digraphs, while ℓ(D) ≥ n-1 guarantees a temporal path between any ordered pair.The pairwise path bound is tight: n-2 copies of a directed n-cycle do not let a vertex reach its predecessor.Source: §3.1 · p. 6
  • ℓ(D) ≥ 2n-3 guarantees a temporal walk in at least one direction between every pair in an always-unilateral digraph, and this threshold is tight.At lifetime 2n-4, examples exist with a pair having no temporal walk in either direction.Source: §3.1 · pp. 6–7
  • ℓ(D) ≥ 2n-k-1 guarantees that some vertex in any k-vertex set S can temporally reach every vertex of S, and this bound is tight.The result supplies the step used to construct the temporal walk visiting a chosen set.Source: §3.1 · pp. 8–9
  • For an always-unilateral temporal digraph D on n vertices and any k-vertex set S, if ℓ(D) ≥ sum_{i=2}^k t14(n,i) ∈ O(kn + k^2), then a temporal walk W visits every vertex in S.When S = V(D), a lifetime of (3n^2 − 7n)/2 is sufficient to guarantee a temporal exploration.Source: §3.1 · pp. 9–10

3.2 Constructions with large lifetime and no temporal exploration

  • ℓ(D) ≥ n^2/9 can fail to yield any temporal exploration in always-strong digraphs with identical snapshots and maximum underlying degree 3.Such examples exist for arbitrarily large orders.Source: §3.2 · pp. 10–11
  • ℓ(D) ≥ n^2/128 can fail to yield temporal exploration in always-unilateral digraphs whose snapshots are directed paths.The construction has underlying maximum degree at most 3, so each directed-path snapshot has maximum undirected degree at most 2.Source: §3.2 · p. 11
  • For every n, a temporal digraph on n + 1 vertices has 1/2 n(n + 1) − 1 snapshots, directed-path snapshots, and no temporal exploration.Every v_j for j ≥ 1 has degree at most 3 in the underlying graph.Source: §3.2 · pp. 11–13
  • The gadget graph W_n has 7n − 6 vertices, maximum degree 3, terminals of degree at most 2, and Hamiltonian paths between s_1 and each s_i.These properties support the construction that bounds the underlying degree while preserving the no-exploration obstruction.Source: §3.2 · pp. 13–14
  • Theorem 2’s construction yields a temporal digraph with maximum undirected degree 3, directed-path snapshots, and no temporal exploration.It combines the no-exploration construction with a linear-size gadget.Source: §3.2 · p. 14
  • The authors leave open whether Theorem 2 can be strengthened to always-strong temporal digraphs.Source: §3.2 · p. 15
  • If an always-unilateral temporal digraph has maximum undirected degree 2 and lifetime at least 2n − 3, it admits a temporal exploration.The proof reduces snapshots to directed Hamiltonian paths around a cycle and applies the pigeonhole principle.Source: §3.2 · p. 15

4 Semicomplete temporal digraphs

This section studies temporal exploration in semicomplete temporal digraphs, establishing a sharp lifetime threshold and examining computational hardness. For temporal tournaments, it reports NP-hardness of deciding whether exploration exists and rules out polynomial-time approximation within a factor of 4/3−ε unless P=NP.

4.1 Minimum lifetime guaranteeing a temporal exploration

  • Every semicomplete temporal digraph D of order n ≥ 2 with lifetime ℓ(D) ≥ ⌊4n/3 − 1⌋ admits temporal exploration; for every n ≥ 2, some temporal tournament with lifetime ⌊4n/3 − 2⌋ does not.Source: §4.1 · p. 18

4.2 NP-hardness

  • Deciding whether a temporal tournament admits an exploration is NP-hard, including when its lifetime is |V(D)| - 1.The section reduces from PrescribedHamiltonianPath, which is NP-hard even when the first prescribed vertex is at position 1 and successive prescribed positions differ by at least 2.Source: §4 · p. 15, §4.2 · pp. 19, 21
  • TemporalExploration is NP-hard even when the input is a temporal tournament with exactly n−1 snapshots.The reduction from PrescribedHamiltonianPath preserves whether a prescribed Hamiltonian path exists by encoding each prescribed vertex as a consecutive triple in the temporal exploration.Source: §4.2 · pp. 22–23

4.3 Inapproximability

  • For every ε > 0, FastestTemporalExploration cannot be approximated within 4/3−ε on temporal tournaments unless P=NP.The reduction creates a gap: if the input tournament admits an exploration, the constructed instance needs at most n + 3N − 1 snapshots; otherwise, every exploration needs at least n + 4N snapshots.Source: §4.3 · pp. 25–26

5 Large minimum degree

For always-strong temporal digraphs with bounded minimum-degree deficiency, the section develops an O(cn) exploration bound and shows it is asymptotically tight. A simpler approach first gives an O(cn log n) bound, while travel plans support the sharper construction.

5 Large minimum degree

  • O(cn) snapshots suffice for temporal exploration in always-strong digraphs with deficiency at most c, and the bound is asymptotically tight.Here deficiency is the maximum, over snapshots, of n−1 minus the minimum undirected degree; deficiency zero means every snapshot is semicomplete.Source: §5 · p. 26

5.1 Simpler upper-bound

  • (3c + 7)n log n snapshots suffice as a simpler upper bound for always-strong temporal digraphs with deficiency at most c.The proof repeatedly covers a fraction of the unexplored vertices and uses strong connectivity to join the resulting walks.Source: §5.1 · p. 29

5.2 Travel plan

  • Travel plans address the risk that early walk choices consume vertices useful to later walks, while the one-set gap supplies intermediate connectivity.The construction places vertices not reachable by every member of a selected set into intermediate plan sets.Source: §5.2 · pp. 30–31
  • A travel plan partitions vertices into ordered sets so choices from sufficiently separated sets can be visited in order by one temporal walk.The construction yields gap 1, width O(c), and order Ω(n/c) within a lifetime Θ(n).Source: §5.2 · pp. 30–31

3. Vi+1 \ RHi

The construction uses travel plans and connecting paths to assemble an exploration, then establishes a matching-order obstruction with strongly connected snapshots. Its lower-bound example repeats a temporal digraph in which certain marked vertices cannot reach one another in the required order.

3. Vi+1 \ RHi

  • The construction of a gap-1 travel plan makes each later target reachable either directly from an earlier plan set or through an intermediate set.For a starting vertex in Bi, the proof routes through a vertex in Ai+1 before reaching the target in Hi+1.Source: §3 · p. 32

5.3 Tight bounds

  • The probabilistic step assigns vertices among several travel plans while avoiding pairs that lie in the same or consecutive plan sets.A bounded-degree auxiliary graph captures these incompatible choices; sufficiently many such graphs admit a partition into independent sets.Source: §5.3 · p. 33
  • The travel-plan walks can be joined by paths in strongly connected snapshots to form a temporal exploration.The proof assigns vertices to independent sets of auxiliary graphs, visits each assigned set within its plan, and connects successive walks.Source: §5.3 · p. 33
  • Theorem 8’s construction has strongly connected snapshots and deficiency at most c, yet admits no temporal exploration over c(n−c−2) snapshots.It repeats a sequence of snapshots; among c+1 marked vertices, two first appearances fall in one repeated block, contradicting the required temporal reachability order.Source: §5.3 · p. 34

6 Future work

The future-work section poses conjectures and open questions about temporal exploration, including degree-bounded digraphs, large-minimum-degree settings, and travel plans.

6 Future work

  • Maximum degree 2 remains unresolved for always-strong temporal digraphs, although Proposition 15 rules out subquadratic lifetime at maximum degree 3.The section also conjectures an O(n log n) lifetime bound for temporal digraphs whose snapshots are directed cycles; an Omega(n log n) lower bound is known, and the degree-3 case remains open.Source: §6 · pp. 34–35

large minimum degree.

  • For always-unilateral digraphs with bounded average minimum degree, the authors conjecture that a lifetime f(c)n^(2−epsilon) suffices for some 0 < epsilon <= 1.They suggest that the reachability digraph may help connect intermediate walks: both strongly connected and acyclic reachability digraphs are described as favorable cases.Source: large minimum degree · p. 35, §6 · p. 35
  • The authors ask whether Theorem 7 can extend to parameters smaller than average minimum degree, such as the largest independent-set size in any snapshot.They conjecture a subquadratic lifetime bound, f(k)n^(2−epsilon), for always-strong digraphs whose snapshots have no independent set larger than k.Source: large minimum degree · p. 35
  • The authors ask when temporal graphs admit travel plans of small width and gap, noting that they know of no similar auxiliary structure used for undirected temporal exploration.The travel-plan definition transfers naturally to the undirected setting.Source: large minimum degree · p. 35

Related papers

Loading 2609.34339v2…