(Last updated: Sep 22, 2026.)

This page lists a few open questions in temporal graphs that (so far) humans and LLMs couldn’t solve.

Problem 1: Spanners of size 2n-3 in temporal cliques

A temporal clique is a temporal graph whose footprint is a complete graph. Given a temporal clique in which every edge has exactly one time label, the question is whether, for all labelings, it always admits a spanner of size \(2n-3\) (subset of edges that preserves temporal reachability for all pairs).

The following formulations are equivalent for this problem (pick your preferred option):

  1. The labeling is arbitrary and temporal path are non-strict (non-decreasing).
  2. The labeling is proper (adjacent edges have a different label) and temporal paths are increasing.
  3. The labeling is an arbitrary permutation of the edges (in \([1,{n \choose 2}]\)) and temporal paths are increasing.

Here is an example with \(2n-3\) edges (using the third formulation):

Temporal clique          Temporal spanner

Example of a temporal clique and one of its spanners (of size 2n-3).

In [CPS19&21], Joseph Peters, Jason Schoeters and I showed that spanners of size \(O(n \log n)\) always exist in temporal cliques. We had two main open questions:

  • Weak conjecture (Question 1 in [CPS21]): Do spanners of size \(O(n)\) always exist?
  • Strong conjecture (Question 2 in [CPS21]): Do spanners of size \(2n-3\) always exist?

The weak conjecture has been solved by Júlia Baligács [B26]. Namely, temporal cliques always admit spanners of size \(7n\). With the help of AI, the analysis in this paper can be refined to \(6n\) (perhaps slightly less), which is anecdotal as it uses the same algorithm.

The main question is now whether \(2n-3\) is always achievable. Presumably, this will require new ideas. So far, no counter-example was found, and we know experimentally that no counter-example exists up to \(n=8\) included. Precisely, all temporal cliques on \(\le 8\) vertices admit spanners of size \(2n-4\) or \(2n-3\).

Call for contributors

If you have partial results in this direction, please feel free to contact me.

References

  • A. Casteigts, J. Peters, J. Schoeters, Temporal cliques admits sparse spanners (ICALP 2019, JCSS 2021) – [arxiv]
  • J. Baligács, Temporal cliques admits linear spanners (2026) – [arxiv]
  • S. Angrick, B. Bals, T. Friedrich, H. Gawendowicz, N. Hastrich, N. Klodt, P. Lenzner, J. Schmidt, G. Skretas, A. Wells, How to reduce temporal cliques to find sparse spanners (ESA 2024) – [arxiv]
  • A. Casteigts, D. Carnevale, T. Corsini, Dismountability in temporal cliques revisited (SAND 2025) – [arxiv]
  • D. Bilò, G. D’Angelo, L. Gualà, S. Leucci, M. Rossi, Sparse temporal spanners with low stretch (ESA 2022) – [arxiv]

Problem 2: Shortest temporal exploration problem

The input to this problem is a temporal graph whose snapshots are all connected (class \(\texttt{AC}\): Always-Connected). The input is entirely known before hand. An agent is placed at one of the vertices adversarially. In each snapshot \(G_i\), we can move the agent from its current location to a neighbor vertex in \(G_i\), or leave it in place. There is at most one move per snapshot. The goal is to visit all the vertices (i.e. explore the graph) using as few moves as possible.

Example of a graph \(\mathcal{G} \in \texttt{AC}\):

Always-connected graph


This problem was introduced by Balev, Sanlaville, and Toullalan [BST25]. They showed that an exploration with \(O(n^{1.5})\) moves always exist if the lifetime \(L\) (number of snapshots) of the graph is at least \(\Theta(n^{3.5})\). In the journal version [BST26], they improve this result to requiring only lifetime \(\Theta(n^{2})\). The main questions in this work are the following:

  • Weak conjecture (Conjecture 1 in [BST26]): Does an exploration of \(O(n)\) moves exist when \(L=\Theta(n^2)\)?
  • Strong conjecture (Conjecture 2 in [BST26]): Does an exploration of \(2n-3\) moves exist when \(L={n \choose 2}\)?

Funnily enough, the two bounds in these questions are the same as in Problem 1 above. However, this seems to be accidental, as both problems are quite different. Note that, so far, even an exploration with \(O(n \log n)\) moves is not known to be guaranteed.

Some comments

  • If the graph is static (i.e. all \(G_i\)s are the same), then there exists a \(2n-3\) solution – essentially a DFS in the graph without the last return to the initial vertex.
  • If the graph has a sufficiently large lifetime, then at least one graph must repeat at least \(2n-3\) times, so we could decide to move only when the snapshot is \(G_i\), so a solution of length \(2n-3\) also exists.
  • The \(\Theta(n^2)\) bound on the lifetime is natural, as it guarantees that an exploration exists. The argument is simple: for any \(u,v \in V\), the agent can move from \(u\) to \(v\) in at most \(n-1\) time steps, then we can compose such movements along an arbitrary permutation of the vertices.
  • More edges gives more power, so one may assume wlog for this problem that all the snapshots are trees.

References