Notions of isomorphism and equivalence of temporal graphs serve as tools to compare individual temporal graphs as well as entire classes of temporal graphs.

There are different types of temporal isomorphisms depending on the property that is preserved. These may all be called $x$-isomorphism. approved by Dagstuhl 26251 (06/2026)

In the static graphs, graph isomorphism and other relations captures structural equivalence.

For temporal graphs, different notions of structural equivalence have been introduced capturing different notions of the temporal structure.

Temporal graphs come with several definitional choices — directed vs. undirected, strict vs. non-strict, proper vs. arbitrary, and simple vs. multi-labeled (see Temporal Graph Settings) — each of which affects the structure that can be expressed. One prominent application of temporal equivalence notions is comparing these temporal graph settings systematically:

When can every graph in one setting be transformed into an equivalent graph in another?

Each equivalence notion is best understood as preserving a particular invariant. This gives four increasingly coarse notions: bijective equivalence preserves temporal paths with multiplicity and support — it corresponds to an isomorphism of labelled graphs where the label-order has to be preserved; support equivalence preserves which static paths occur as the support of temporal paths; reachability equivalence preserves the reachability digraph; induced-reachability equivalence preserves the reachability digraph only on the original vertices, allowing auxiliary vertices.

History on temporal isomorphism notions

Literature on temporal isomorphism notions

<aside> ‼️

TODO: update the following to $x$ preserving isomorphism

</aside>

Equivalence relations and their quasi-orderings

Let $\mathcal{G}_1 = (V_1, E_1, \lambda_1)$ and $\mathcal{G}_2 = (V_2, E_2, \lambda_2)$ be temporal graphs. Denote by $\mathcal{P}(\mathcal{G}_1)$ and $\mathcal{P}(\mathcal{G}_2)$ the sets of all temporal paths in $\mathcal{G}_1$ and $\mathcal{G}_2$, respectively. Two temporal paths $P$ and $P'$ share the same support if they visit the same vertices in the same order, i.e., their underlying static paths are identical.

<aside> 💡

Definition.

$\mathcal{G}_1$ and $\mathcal{G}_2$ are bijectively equivalent, denoted $\mathcal{G}_1\sim_B\mathcal{G}_2$, if there exist a vertex bijection $\sigma\colon V_1\to V_2$ and a bijection $\varphi \colon\mathcal{P}(\mathcal{G}_1)\to\mathcal{P}(\mathcal{G}_2)$ such that, for every temporal path $P=(v_0,\ldots,v_k)$ in $\mathcal{G}_1$, the support of $\varphi(P)$ is $(\sigma(v_0),\ldots,\sigma(v_k))$.

$\mathcal{G}_1$ and $\mathcal{G}_2$ are support equivalent, denoted $\mathcal{G}_1\sim_S\mathcal{G}_2$, if there exists a vertex bijection $\sigma\colon V_1\to V_2$ such that, for every temporal path $P=(v_0,\ldots,v_k)$ in either graph, the other graph contains a temporal path with the corresponding support under $\sigma$ or $\sigma^{-1}$, respectively.

$\mathcal{G}_1$ and $\mathcal{G}_2$ are reachability equivalent, denoted $\mathcal{G}_1\sim_R\mathcal{G}_2$, if there exists a vertex bijection $\sigma\colon V_1\to V_2$ such that $(u,v)\in E(\mathcal{R}(\mathcal{G}_1))$ if and only if $(\sigma(u),\sigma(v))\in E(\mathcal{R}(\mathcal{G}_2))$.

$\mathcal{G}_2$ is induced-reachability equivalent to $\mathcal{G}_1$, denoted $\mathcal{G}1\sim{iR}\mathcal{G}_2$, if there exists an injection $\iota\colon V_1\to V_2$ such that $(u,v)\in E(\mathcal{R}(\mathcal{G}_1))$ if and only if $(\iota(u),\iota(v))\in E(\mathcal{R}(\mathcal{G}_2))$.

</aside>

Let $\mathbb{S}$ and $\mathbb{T}$ be temporal graph classes and let $X \in \{B, S, R, iR\}$.

• $\mathbb{S}$ is simulated under $X$ by $\mathbb{T}$ if for every $\mathcal{G}\in\mathbb{S}$ there exists $\mathcal{H}\in\mathbb{T}$ such that $\mathcal{G}\sim_X \mathcal{H}$.
• $\mathbb{S}$ and $\mathbb{T}$ are equivalent under $X$ if $\mathbb{S}$ is simulated under $X$ by $\mathbb{T}$ and vice versa.
• $\mathbb{T}$ is strictly more expressive under $X$ than $\mathbb{S}$ if $\mathbb{S}$ is simulated under $X$ by $\mathbb{T}$ but $\mathbb{T}$ cannot be simulated by $\mathbb{S}$.
• $\mathbb{S}$ and $\mathbb{T}$ are incomparable under $X$ if neither can be simulated by the other.

Each equivalence relation forms a quasi-order on the temporal graph classes defined by the temporal settings.

<aside> 💡

Definition.

A quasi-ordering (or preorder) on a set $S$ is a binary relation $\leq$ that is reflexive ($a \leq a$) and transitive ($a \leq b$ and $b \leq c$ implies $a \leq c$). Unlike a partial order, it need not be antisymmetric: two distinct elements can satisfy $a \leq b$ and $a\geq b$ simultaneously.

</aside>

The Hasse diagram of the quotient by mutual transformability is the corresponding $X$-hierarchy. These hierarchies inherit the equivalence chain $\sim_B \Rightarrow \sim_S \Rightarrow \sim_R$. As $X$ becomes coarser, the hierarchy also becomes coarser: the $B$-hierarchy is the finest, while the $iR$-hierarchy collapses all 12 settings.

The resulting hierarchies have practical implications: positive algorithmic results in more expressive settings transfer to weaker settings, and hardness results in weaker settings propagate to stronger ones.

Quasi-order under bijective-equivalence — coincides with the subset-inclusion lattice of settings.

Quasi-order under support-equivalence — adds non-strict $\rightsquigarrow_S$ proper via support-dilation.

Note on bijective vs. support equivalence. The difference lies in multiplicities. Bijective equivalence requires a bijection between the path sets so the two graphs must have identical multisets of path-supports. Support equivalence only asks that the sets of path-supports agree under $\sigma$. Example: if $\mathcal{G}_1$ has two temporal paths from $a$ to $b$ through $c$ while $\mathcal{G}_2$ has only one, they are support equivalent but not bijectively equivalent.