some comments on their interpretation and use
CCS24 introduced four notions of equivalence of two graphs in terms of reachability, which capture the equivalence with decreasing strength: Bijective, Support, Reachability, and induced-Reachability equivalence.
<aside> <img src="/icons/error_lightgray.svg" alt="/icons/error_lightgray.svg" width="40px" />
Definition: (Bijective equivalence). Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two temporal graphs built on a same set of vertices. These graphs are bijectively equivalent if there is a bijection σ between the set of journeys of $\mathcal{G}_1$ and that of $\mathcal{G}_2$, and σ is support-preserving.
</aside>
Too strong to be interesting, basically isomorphism of reachabilities. Will not be considered further.
<aside> <img src="/icons/error_orange.svg" alt="/icons/error_orange.svg" width="40px" />
Definition: (Support equivalence). Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two temporal graphs built on the same set of vertices. These graphs are support-equivalent if for every journey in either graph, there exists a journey in the other graph whose underlying path goes through the same sequence of vertices.
</aside>
Transformation of one graph into the other so that for any pair of vertices in the first graph, at least one connecting reachability-path visits exactly the same intermediate vertices in the second graph.
<aside> <img src="/icons/error_red.svg" alt="/icons/error_red.svg" width="40px" />
Definition: (Reachability equivalence). Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two temporal graphs built on the same set of vertices. $\mathcal{G}_1$ and G2 are reachability-equivalent if $\mathcal{R}(\mathcal{G}_1)\simeq\mathcal{R}(\mathcal{G}_2)$ (i.e., both reachability graphs are isomorphic). By abuse of language, we say that $\mathcal{G}_1$ and $\mathcal{G}_2$ have the “same” reachability graph.
</aside>
Weaker transformation, where it is just important to obtain the same set of reachabilities. How $x$ visits $y$ is not important.
<aside> <img src="/icons/error_yellow.svg" alt="/icons/error_yellow.svg" width="40px" />
Definition: (Induced reachability equivalence). Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two temporal graphs built on vertices $V1$ and $V_2$, respectively, with $V_1 \subseteq V_2$. $\mathcal{G}_2$ is induced-reachability equivalent to $\mathcal{G}_1$ if $\mathcal{R}(\mathcal{G}_2)[V_1] \simeq \mathcal{R}(\mathcal{G}_1)$. In other words, the restriction of $\mathcal{R}(\mathcal{G}_2)$ the vertices of $V_1$ is isomorphic to $\mathcal{R}(\mathcal{G}_1)$.
</aside>
Weakest transformation, where one is additionally allowed to add vertices and edges to match the set of reachabilities.
Look at $\delta$ edge connected components (Ben)
Ask Ben to give you the table slides, steal the way to present the table