[Reachabilities Impacted by Temporal Graph Settings — [CCS24] and [D25]](https://temporalgraph.notion.site/Reachabilities-Impacted-by-Temporal-Graph-Settings-CCS24-and-D25-11843d6e8b7c8041a9cde87728cfea59)

In traditional static graph theory, one can usually choose between single- vs multi-edges —with the former being the standard— and directed vs undirected edges. Additionally, one can add weight to edges or vertices, but this is regarded as an addon to a classic (simple/multi-) (un)directed graph.

In temporal graph theory, the time-dimension adds at least two more properties, leading up to the following settings formally discussed by Casteigts, Corsini, Sarkar in 2024. Untoggle the entries for a definition.

• directed vs undirected edges
• strict vs non-strict reachability
• simple vs multi-labeled
• restricted to proper vs not restricted

The hierarchy of temporal settings with respect to reachability equivalence. An arrow $A\rightarrow B$ represents that for every temporal graph in $A$, there exists a reachability equivalent temporal graph in $B$. This relation is transitive. Apart from omitted transitive arrows, every non-existent arrow is proven to be impossible (excluding the open question).

Illustration of the seperation between settings (non-strict is extended by strict — undirected is extended by directed)

Venn diagram corresponding to the reachability-equivalence hierarchy on the left. The entry in each space names the setting of the corresponding smallest triangle.

We now discuss the setting-choices and their intricate difference to static graph theory.

(2) simple vs multi-labeled

In contrast to static graphs, most literature claims the multi-labeled setting to be the general one and claims the simple temporal graphs to be a special case. For some computational problems it makes a difference cite for some others is does not cite. [CCS24] showed that for undirected graphs in terms of reachability […].

(3) strict vs non-strict reachability

This is a heavily discussed setting-choice for a computational problem. As many papers emphasized already, it can have a significant impact on the computational complexity of a problem and even change the definition of structures completely […]. The main differences in my eyes are the following:

• strict implies a direction of paths/reachabilities
• non-strict allows for temporal cycles (and as we know from static graph theory: cycles are bad)
• strict allows “isolating” reachabilities by applying the same time label to every edge

It is most definitely important to connect this setting-choice to the situation one intends to model. In the strict setting, the traversal of an edge takes some amount of time which happens for example when a physical object/subject is involved — vehicle transporting something or someone; […]. In the latter, traversal is instant so that another traversal is possible right away — people communicating one hour at a time; infections spreading; […].

(4) restricted to proper vs not restricted

This setting is quite nice as the distinction of strict vs non-strict becomes irrelevant as every journey is a strict journey in a proper graph.

Furthermore, a simple and proper temporal graph is most restricted. If a computational problem is hard already for happy (simple and proper) graphs, then it is hard for strict and for non-strict graphs.