Improved Exploration of Temporal Graphs

Basic Information

• Paper ID: 2511.22604
• Title: Improved exploration of temporal graphs
• Authors: Paul Bastide (University of Oxford), Carla Groenland (TU Delft), Lukas Michel (University of Oxford), Clément Rambaud (Université Côte d'Azur)
• Classification: cs.DS (Data Structures and Algorithms), math.CO (Combinatorics)
• Publication Date: November 27, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.22604

Abstract

Temporal graphs are sequences of graphs on the same vertex set. The temporal exploration problem seeks to find the shortest sequence of moves from a given vertex that visits all vertices, where at each time step one can either stay at the current vertex or move to an adjacent vertex in the current snapshot graph. For the fundamental case where each snapshot is connected and has bounded maximum degree, this paper improves the previous O(n^(7/4)) bound to O(n^(3/2)√log n). More generally, introducing the concept of "average temporal maximum degree" D, we prove an upper bound of O(n^(3/2)√(D log n)), which is the first subquadratic bound when the underlying graph has bounded average degree, and simultaneously improves known best bounds for planar graphs, bounded treewidth graphs, and other cases.

Research Background and Motivation

1. Core Problem

The temporal graph exploration problem (TEXP) studies how an agent can visit all vertices as quickly as possible in a dynamically changing network. This problem originates from the fact that many real-world networks evolve over time, such as communication networks, power grid designs, and metabolic networks, which cannot be captured by static graph models.

2. Problem Significance

• Theoretical Importance: Temporal graph exploration is central to temporal graph reachability problems, relating to fundamental questions in complexity theory and combinatorial optimization
• Practical Applications: Direct applications in dynamic network routing, mobile agent navigation, and sensor network coverage
• Complexity Challenges: Even in always-connected temporal graphs, approximating the shortest exploration length within an O(n^(1-ε)) factor is NP-hard

3. Limitations of Existing Methods

• Degree-Restriction Methods: Erlebach and Spooner (2018) gave O((n² log d)/log n) bound, improved by Erlebach et al. (2019) to O(n^(7/4))
• Structure-Restriction Methods: O(kn^(3/2) log n) for graphs with treewidth k, O(n^(7/4) log n) for planar graphs
• Limitations: Various methods are not unified, and there remains a significant gap from the known Ω(n log n) lower bound

4. Research Motivation

The authors note that the bounded-degree snapshot case is considered the "most fundamental case." This paper aims to:

• Significantly improve the upper bound for bounded-degree cases
• Provide a unified framework for handling multiple structural constraints
• Give the first subquadratic bound when the underlying graph has bounded average degree

Core Contributions

1. Main Theoretical Result (Theorem 1.1): For any always-connected temporal graph with n vertices and average temporal maximum degree D, there exists an exploration path of length O(n^(3/2)√(D log n))
2. Improvement for Bounded-Degree Snapshots (Corollary 1.2): When each snapshot has maximum degree ≤ d, the exploration length is O(n^(3/2)√(d log n)), significantly improving the previous O(n^(7/4)) bound
3. First Subquadratic Bound for Bounded Average Degree (Corollary 1.3): When the underlying graph has average degree ≤ k, we give an O(n^(3/2)√(k log n)) bound, the first subquadratic result in this setting
4. Unified Improvements for Multiple Special Cases:
   • Planar graphs: O(n^(3/2)√log n), improving previous O(n^(7/4) log n)
   • Graphs with treewidth k: O(n^(3/2)√(k log n)), removing the √(k log n) factor
   • K_t-minor-free graphs: O(t^(1/2) log^(1/4) t · n^(3/2)√log n)
   • Graphs with o(n²/log n) edges: o(n²) time exploration
5. Algorithmic Realizability: All theoretical results can be converted to polynomial-time algorithms

Method Details

Task Definition

Temporal Graph: G = (G_t)_{t∈I}, where I⊆ℕ is a time interval, all G_t share vertex set V but may have different edge sets

Temporal Walk: A vertex sequence W = (w_ℓ,...,w_{r+1}) such that for each t∈ℓ,r, either w_t = w_{t+1} or w_t w_{t+1} ∈ E(G_t)

Temporal Exploration: A temporal walk starting at time step 1 that covers all vertices

Average Temporal Maximum Degree: D = (Σ_{v∈V} max_{t∈I} d_(v))/n

Core Technical Framework

The proof employs a hierarchical lemma structure, progressively building toward the final result:

1. Fundamental Lemma: Connecting Unvisited Vertices in Short Time (Lemma 2.1)

Core Idea: Within a sufficiently long time interval, there must exist a temporal walk path between two vertices in the unvisited set X.

Key Mechanism: Using a "recording" strategy

• For each u∈X and time t, define:
  • F(u,t) = set of vertices reachable from u (within time ℓ,t)
  • B(u,t) = set of vertices that can reach u (within time t,r)
• If F(u,t-1)∩B(u,t+1) ≠ V(G), by connectivity there exists a neighbor w_{u,t} on the boundary
• u "records" w_{u,t} at time t

Counting Argument:

• Each vertex is recorded by the same u at most twice (otherwise contradiction)
• Total records = |X|·|I| > 2Dn = 2Σ d_max(w)
• There must exist a vertex w recorded more than 2d_max(w) times
• This means more than d_max(w) different vertices in X recorded w
• By pigeonhole principle, find a connection path between two vertices u,v∈X

Quantitative Result: If |I| ≥ 2Dn/|X| + 1, then there exists a temporal walk between u,v∈X

Tightness: The authors construct a grid-plus-leaves example (Figure 1) proving the constant factor is tight

2. Covering Lemma: Finding Small "Base Station" Set (Lemma 2.2)

Objective: Find a small subset S of X such that every vertex in X is reachable from some vertex in S

Recursive Construction:

• Initialize X_0 = X
• Iteratively select v_i∈X_ such that |F(v_i)∩X_| ≥ |B(v_i)∩X_|
• Define X_i = X_ \ (F(v_i)∪B(v_i)∪{v_i})
• Continue until X_ℓ = ∅

Key Observations:

• By Lemma 2.1, no two vertices in the selected {v_i} have a temporal walk between them, so ℓ < k
• There exists some i such that |F(v_i)∩X| ≥ |X|/(2k) - 1
• Remaining set X' = X(F(v_i)∪{v_i}) satisfies |X'| ≤ (1-1/(2k))·|X|

Inductive Result: |S| ≤ log|X|/(-log(1-1/(2k))) ≤ 2k log|X|

Parameter Choice: Take k = ⌈√(D·|X|/log|X|)⌉

3. Batch Covering Lemma (Lemma 2.3)

Strategy: Cover Ω(√(|X|/(D log|X|))) vertices within n time steps

Implementation:

• Divide n steps into m = ⌊√(|X|/(8D log|X|))⌋ intervals
• Each interval has at least ⌊n/m⌋ ≥ 2Dn/k + 1 steps
• Apply Lemma 2.2 to X(S_1∪...∪S_) in the i-th interval
• Obtain set |S_i| ≤ 2k log|X|

Path Construction:

• There exists v_{m+1}∈X(S_1∪...∪S_m) (since Σ|S_i| < |X|/2)
• Backward construction: v_i∈S_i can reach v_{i+1} (within interval I_i)
• Concatenate to obtain a walk covering at least m+1 distinct vertices

Technical Innovations

1. Unified Degree Metric: Average temporal maximum degree D unifies snapshot degree restrictions and underlying graph sparsity
2. Elegant Recording Mechanism Design:
   • Establishes connections via boundary vertices of F(u,t-1)∩B(u,t+1)
   • Bidirectional reachability ensures special properties of recorded vertices
   • Each vertex recorded by each source at most twice is key
3. Recursive Decomposition Strategy:
   • Lemma 2.2's recursive construction avoids direct handling of entire X
   • Balanced selection of forward and backward reachable sets ensures geometric shrinking
4. Fine-Grained Time Interval Partitioning:
   • Uses different "base station" sets S_i in different intervals
   • Ensures vertices on exploration path are distinct
   • Connects intervals using n-1 steps (via Lemma 2.4)
5. Iterative Doubling Technique (Theorem 1.1 proof):
   • Constructs sequence X_0⊇X_1⊇X_2⊇...
   • Each iteration reduces unvisited set size by √(|X_i|/(D log|X_i|))/8
   • Time steps allocated as 2^i·n, total time O(n^(3/2)√(D log n))

Experimental Setup

Note: This is a pure theory paper with no experimental section. All results are derived through rigorous mathematical proofs. The paper provides:

Theoretical Verification

1. Tightness Examples (Figure 1): Constructs specific temporal graph instances proving Lemma 2.1's bound is tight within constant factors
2. Algorithmic Realizability Statement: All theorems can be converted to polynomial-time algorithms

Parameter Analysis

• Time Complexity: O(n^(3/2)√(D log n))
• Space Complexity: Not explicitly discussed (theoretical proof level)
• Constant Factors: Constants in proof (e.g., 1/8) can be optimized, but paper focuses on asymptotic bounds

Experimental Results

Since this is a theoretical paper, here we summarize comparisons of its theoretical results:

Main Results Comparison

Asymptotic Behavior Analysis

Subquadratic Condition: When D = o(n/log n), O(n^(3/2)√(D log n)) = o(n²)

Concrete Examples:

• D = O(1) (constant degree): O(n^(3/2)√log n) vs O(n^(7/4))
• D = √n: O(n^(7/4)√log n) vs O(n^(7/4))
• D = n/log n: O(n²/√log n) vs O(n^(7/4)) (still subquadratic)

Lower Bound Comparison

The paper discusses known lower bounds:

• General case: Ω(n²) (star construction)
• Bounded degree: Ω(dn) (extended star construction)
• Path snapshots/planar graphs: Ω(n log n)

Bound Gap:

• For constant degree: upper bound O(n^(3/2)√log n) vs lower bound Ω(n log n)
• Still has gap of √n/log^(1/2) n

Related Work

1. Development of Temporal Graph Exploration

Problem Origins:

• Michail and Spirakis (2016) introduced TEXP problem
• Proved NP-hardness in general case

Complexity Theory:

• Approximation hardness: O(n^(1-ε)) approximation is NP-hard EHK21
• NP-hardness for pathwidth 2 decision problem BZ19

2. Upper Bound Research Direction

Degree Restriction Direction:

• Erlebach & Spooner (2018): O((n² log d)/log n), first subquadratic bound
• Erlebach et al. (2019): O(n^(7/4)), major improvement
• This Paper: O(n^(3/2)√(d log n)), further improvement

Structure Restriction Direction:

• Treewidth k: O(k^(1.5)n^(1.5) log n) EHK15 → O(kn^(3/2) log n) AGMZ22 → O(n^(3/2)√(k log n)) This Paper
• Planar graphs: O(n^(1.8) log n) EHK21 → O(n^(7/4) log n) AGMZ22 → O(n^(3/2)√log n) This Paper
• Cactus graphs: Linear bound IKW14
• 2×n grids: Near-linear bound EHK21

3. Lower Bound Constructions

• Star graphs: Ω(n²) EHK15
• Degree d graphs: Ω(dn) EHK15
• Path snapshots: Ω(n log n) AGMZ22, EHK15

4. Random Models

Baguley et al. (2025) study random temporal graphs:

• Random tree model: High probability O(n^(3/2)) exploration
• Optimal for star distribution

5. Related Variants

• Exploration with edge count restrictions BST25
• Cases with fewer edge removals ES22
• Cases with longer edge persistence IW13
• Parameterized complexity ES23, AFGW23

This Paper's Position

This paper's unique contributions are:

1. Unified Framework: Average temporal maximum degree D encompasses multiple previously independently studied cases
2. Technical Breakthrough: The combination of recording mechanism and recursive decomposition is novel
3. Broad Improvements: Simultaneously improves bounds for multiple important special cases

Conclusions and Discussion

Main Conclusions

1. General Theorem: An n-vertex always-connected temporal graph with average temporal maximum degree D can be explored in O(n^(3/2)√(D log n)) steps
2. Methodological Contribution: Provides a unified framework for handling both snapshot degree restrictions and underlying graph sparsity
3. Multiple Improvements: Significantly improves known best bounds for bounded degree, planar graphs, bounded treewidth, and other settings

Limitations

1. Bound Tightness:
   • For constant degree, upper bound O(n^(3/2)√log n) vs lower bound Ω(n log n) still has gap
   • Lemma 2.1 is tight within constant factors, but overall construction tightness is unknown
2. Combinatorial Difficulty:
   • Ω(dn) and Ω(n log n) lower bounds are difficult to combine
   • Unclear if lower bound of form f(D)·n log n exists
3. Algorithm Implementation:
   • While claimed to be algorithmizable, no explicit algorithm or runtime analysis given
   • Constant factors may be large
4. Model Assumptions:
   • Requires always-connectivity
   • Assumes agent knows entire temporal graph sequence in advance

Future Directions

The paper explicitly poses open problems (Problem 3.1):

Core Question: Does there exist a function f = ω(1) such that for all n, D≥1, there exists an n-vertex temporal graph with average temporal maximum degree ≤ D whose shortest exploration length is at least f(D)·n log n?

Possible Research Directions:

1. Lower Bound Improvements:
   • Construct new lower bound instances
   • Prove or disprove existence of f(D)·n log n form lower bound
2. Upper Bound Refinement:
   • Remove log n factor
   • Improve constant factors
3. Additional Structural Constraints:
   • Combine average temporal maximum degree with other structural properties
   • Study special temporal graph classes (periodic, regular evolution)
4. Algorithm Implementation:
   • Provide explicit polynomial-time algorithms
   • Analyze actual runtime
   • Experimentally verify theoretical bounds
5. Relaxing Assumptions:
   • Non-always-connected cases
   • Online algorithms (without knowing future snapshots)
   • Fine-grained analysis of random temporal graphs

In-Depth Evaluation

Strengths

1. Theoretical Innovation (★★★★★)

• Unified Framework: Introduction of average temporal maximum degree D is an important conceptual innovation, elegantly unifying previously independent research directions
• Technical Breakthrough: The recording mechanism design is sophisticated, establishing connections via intersection boundaries of forward and backward reachable sets
• Proof Structure: Hierarchical lemma system (Lemma 2.1→2.2→2.3→Theorem 1.1) is clear and modular

2. Breadth of Results (★★★★★)

• Simultaneously improves multiple important special cases (bounded degree, planar graphs, bounded treewidth)
• First subquadratic bound for bounded average degree underlying graphs
• Direct implications for K_t-minor-free graphs and other general classes

3. Mathematical Rigor (★★★★★)

• All proofs are strict and complete
• Provides tightness examples (Figure 1)
• Counting and inductive arguments are meticulous

4. Writing Clarity (★★★★☆)

• Introduction well articulates motivation and contributions
• Proof structure is clear with smooth logical flow
• Figure 2 helps understand recording mechanism
• Notation is clearly defined

5. Impact Potential (★★★★★)

• Significantly advances understanding of a fundamental problem
• Methodology may apply to other temporal graph problems
• Provides clear open problems for future research

Weaknesses

1. Bound Tightness (★★★☆☆)

• Upper bound O(n^(3/2)√log n) vs lower bound Ω(n log n) still has √n/√log n gap
• Unclear which bound is closer to truth
• Optimal bound may differ for different D values

2. Missing Algorithm Details (★★★☆☆)

• While claiming "easily made algorithmic," does not provide:
  • Explicit algorithm description
  • Specific polynomial degree
  • Actual constant factor sizes
• Lacks algorithm pseudocode

3. Practical Relevance (★★☆☆☆)

• Pure theoretical results, no experimental verification
• Constant factors may be large (proof contains 1/8, 2, 4, etc.)
• Requires knowing entire temporal graph sequence in advance (often unrealistic)
• Always-connectivity assumption may not hold in practice

4. Technical Limitations (★★★☆☆)

• Recording mechanism, while clever, seems difficult to improve to O(n log n)
• Recursive decomposition introduces log factor, possibly inherent
• Unexplored whether other techniques (e.g., potential function method) could help

5. Insufficient Lower Bound Analysis (★★★☆☆)

• Only briefly discusses known lower bounds
• Lacks deep analysis of why Ω(dn) and Ω(n log n) are difficult to combine
• Problem 3.1 is well-posed but lacks conjectures or partial results about answer

Impact Assessment

Contribution to Field (★★★★★)

• Theoretical Breakthrough: Significantly improves bounds for fundamental problem, from n^(7/4) to n^(3/2)√log n
• Methodology: Recording mechanism and recursive decomposition combination may inspire solutions to other temporal graph problems
• Unified Perspective: Average temporal maximum degree provides new research viewpoint

Practical Value (★★☆☆☆)

• Limited Direct Application: Constant factors unoptimized, requires knowing future
• Inspirational Value: Theoretical bounds guide practical algorithm design
• Special Cases: May have practical utility for certain structured temporal graphs

Reproducibility (★★★★☆)

• Proof Verifiable: Mathematical proofs complete, can be verified step-by-step
• Algorithm Implementable: While details omitted, principles allow implementation
• Testing Difficult: Lacks standard test sets and experimental methodology

Applicable Scenarios

Theoretical Research

• Temporal Graph Theory: Starting point for studying other temporal graph optimization problems
• Combinatorial Optimization: Coverage and exploration in dynamic networks
• Complexity Theory: Parameterized complexity and approximation algorithms

Potential Application Domains

1. Communication Networks: Route planning in networks with dynamic topology
2. Sensor Networks: Coverage path planning for mobile sensors
3. Social Network Analysis: Information propagation in evolving social networks
4. Traffic Networks: Path planning considering time-varying road conditions

Constraints

• Requires always-connected network
• Requires knowing or predicting future network state
• Suitable for offline planning rather than online decision-making
• Better performance for networks with small degree (D = o(n/log n) gives subquadratic)

Overall Evaluation

Selected References

Works Directly Improved by This Paper

1. EKL+19 Erlebach et al. "Two moves per time step make a difference." ICALP 2019.
   • Source of previous best bound O(n^(7/4))
2. AGMZ22 Adamson et al. "Faster exploration of some temporal graphs." SAND 2022.
   • Previous best results for planar graphs and treewidth bounds

Problem Origins

3. MS16 Michail & Spirakis. "Traveling salesman problems in temporal graphs." TCS 2016.
   • Introduced TEXP problem

Complexity Theory

4. EHK21 Erlebach, Hoffmann & Kammer. "On temporal graph exploration." JCSS 2021.
   • Approximation hardness and multiple upper bound results

Related Random Models

5. BGK+25 Baguley et al. "Temporal exploration of random spanning tree models." arXiv 2025.
   • O(n^(3/2)) bound for random temporal graphs

Graph Theory Foundations

6. Kos84 Kostochka. "Lower bound of the Hadwiger number of graphs by their average degree." Combinatorica 1984.
   • Average degree bounds for K_t-minor-free graphs

Summary: This is a high-quality theoretical computer science paper making significant progress on the fundamental temporal graph exploration problem. Through introducing a unified framework of average temporal maximum degree and employing a sophisticated recording mechanism, the authors improve bounds for multiple important special cases from O(n^(7/4)) to O(n^(3/2)) scale. While gaps remain from known lower bounds and algorithm implementation details are absent, the theoretical contributions are substantial and the methodology is inspirational. The paper is well-suited for researchers interested in theoretical algorithms and combinatorial optimization, and provides clear directions for future research in this field.