While this submission is a draft, it cannot be used by other submissions.

Temporal graphs, temporal settings, traversal times, reachability, and optimal temporal paths

lax-330177·formalized by Michelle Döring · Hendrik Molter·created ·GitHub @c08a322·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Read the annotated paper for a short introduction with the formal definitions, results, and proofs alongside the text.

    We give three representations of finite temporal graphs on a fixed vertex set: (1) a sequence of snapshots, (2) a footprint with finite time labels, and (3) a chronological list of temporal edge occurrences. Equal-time edge occurrences have no prescribed order.

    We define strict and nonstrict temporal walks, paths, reachability and temporal graph settings. Removing a closed segment turns a walk into a shorter walk with the same endpoints. On proper graphs, the departure times of every nonstrict path are already strictly increasing. Examples distinguish paths from walks, simplicity from properness, and illustrate why opposite arcs may share a timestamp.

    An occurrence may have a natural traversal time. Waiting is allowed, the lifetime bounds departure times, and the final arrival may follow the last snapshot. Uniform traversal times one and zero recover strict and nonstrict paths respectively, with the same vertices and departure times, and therefore the same reachability.

    We define five interpretations of optimal temporal paths for a fixed source, target, release time and arrival deadline: shortest, fastest, foremost, latest-departure and minimum-waiting paths. Each objective admits an optimal path whenever the query is feasible. With uniform traversal time c, elapsed time is total internal waiting plus c times the number of hops. Three-vertex examples separate all five optimality predicates for strict temporal paths (uniform traversal time one). For nonstrict paths (uniform traversal time zero), fastest and minimum waiting coincide.

    Guide to the concepts

    • Three representations of temporal graphs defines snapshots, time-labelled footprints and chronological event lists, and proves how to convert between them.
    • Temporal graph settings defines directed and undirected settings, strict and nonstrict modes, and simple, proper and happy labellings.
    • Paths, walks and reachability defines timed walks, paths and reachability. It proves that deleting cycles preserves reachability and that strict and nonstrict paths coincide on proper graphs.
    • Traversal times allows each edge occurrence its own traversal time and proves that uniform times zero and one recover nonstrict and strict paths, respectively.
    • Counterexamples separates simplicity from properness, shows why the proper-path theorem fails for walks, and gives a happy undirected graph with asymmetric, nontransitive reachability.
    • Optimal temporal paths defines shortest, fastest, foremost, latest-departure and minimum-waiting paths and proves that each optimum is attained whenever a feasible path exists.
    • Optimality under uniform traversal times expresses elapsed time in terms of hops and waiting and proves what fastest paths minimize at traversal times zero and one.
    • Three-vertex examples separating path objectives compares routes on a chain and on a triangle to show which optimality criteria can select different paths.
    • The temporal reachability graph records reachable pairs of distinct vertices as arcs of a static digraph.
    View annotated paper

    3 pages · 22 marked passages

    Concepts

    Concept map
    44 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    Proof networkview on GitHub

    100%
    premise files concept fileProven claimClaim from this submissionAll proofs of one concept — hover for individual statements and proofs
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-330177,
      author = {Michelle Döring and Hendrik Molter},
      title = {Temporal graphs, temporal settings, traversal times, reachability, and optimal temporal paths},
      year = {2026},
      howpublished = {Lax Archive, lax-330177},
      url = {https://laxarchive.org/lax-330177/},
      note = {draft},
    }

    References

    1. Arnaud Casteigts, Timothée Corsini and Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theoretical Computer Science, 2024. arXiv:2208.01720
    2. Michelle Döring. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs. In ISAAC, 2025. doi:10.4230/LIPIcs.ISAAC.2025.27

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…