Many real-world problems can be formulated and modeled in the language of graph theory. However, real-world networks are often not static. They change over time. These structures are called dynamic or temporal graphs. Here’s an example of temporal star with four leaves; each one of its edges is active twice except for $cz$ which is active three times.

Temporal graphs have recently become a very active area of research. However, despite having generated many interesting graph- and complexity-theoretic results, nobody seems to have contemplated the question of what a morphism of temporal graphs should be! Let’s think about it together.

Getting to know the characters

I encountered temporal graphs for the first time when Kitty Meeks (she was my PhD supervisor back in Glasgow) showed me an open problem in a paper by Akrida, Mertzios and Spirakis.

The problem had to do with the following algorithmic task called StarExp(k).

We’re given a star graph $S_n$ with $n$ leaves and an integer $k$ . The edges of the star appear and dissappear over time and each edge $e$ is labeled with a list $\lambda(e)$ of length at most $k$ indicating all the times at which it is active. The algorithmic task is to determine whether there is a temporal walk which starts and ends at the center of the star and which visits every leaf.

It sounds easy, right? After all, in the static case it’s a non-question: the answer is alwasy yes since stars are connected.

So how hard is it?

Akrida, Mertzios and Spirakis showed that you can solve it in polynomial time for $k$ at most three. They also showed that the problem is NP-hard for $k$ at least six. The $k \in \{4,5\}$ cases were left open, but Kitty and I filled-in the gap and showed that they too are NP-hard (by the way, you can read about how we obtained this complexity dichitomy here).

When Kitty first showed me this paper , I was surprised by just how much harder problems get when passing from the static setting to the temporal one. I didn’t realize this at the time, but this is a well known phenomenon.

The challenge

Coming from parameterized complexity theory, the first question I ask when confronted with an NP-hard problem is: “are there any classes of inputs for which the problem becomes tractable? And if so, what do they look like structurally?”

Since the input graphs to the StarExp(k) problem are stars, restricting the graph-theoretic structure of the problem isn’t going to help; stars are pretty much as simple as it gets. So the hardness is coming entirely from the scheduling problem encoded by the temporal data.

In general this seems to be part of a theme for temporal graphs: restricting only the temporal structure or only the graph-theoretic structure is often not enough to achieve tractability.

This observation got me interested in ways of measuring how “structurally complex” a temporal graph is. The problem is that, to be able to speak about structure in some context, you need to know what isomorphism and homomorphism mean in that context; unfortunately this seems to be a question that people haven’t studied yet… so let’s do it!

Morphisms of temporal graphs

Let’s stick to a simple model and assume that our temporal graphs are temporally discrete in the sense that vertices and edges may appear or disappear only in discrete time-steps.

The naïve model: $\mathbf{Gr}^{\mathbb{N}_\leq}$

A first thought would be to model a temporal graph as a functor $\mathcal{G}: \mathbb{N}_\leq \to \mathbf{Gr}$ from the poset of natural numbers to the category of graphs and their homomorphisms. Let’s call this the naïve model of temporal graphs.

In the naïve model, the natural notion of morphism is a natural transformation as in the drawing below.

Notice that vertices and edges can’t really dissappear in this model. Since any temporal graph $\mathcal{G}$ is a functor with the poset of naturals as its domain, the n-th snapshot of $\mathcal{G}(n)$ of $\mathcal{G}$ must have a homomorphism to all of the graphs in the sequence that follow it for all n. This means that, although vertices might merge (because of some non-injective homomorphism at some point in the sequence), you can’t really model a “flashing” vertex which, for example, appears at every even time and disappears at every odd time.

These observations mean that the objects of the naïve model don’t match-up with the temporal graphs I’m trying to study, so I’m ready to move on. However, just to hammer home what’s weird about this model, let’s ask: “how would I write down a temporal path in the naïve model?”

Well, we’d like a temporal path to be a temporal graph whose underlying static graph is a path. In the naïve setting this could be modeled as follows.

But then $\mathcal{P}$ above fails to be isomorphic to the following temporal graph $\mathcal{R}$ which should also be a perfectly good candidate as a temporal path (albeit one where nothing changes between times 1 and 2).

Modifications of the naïve model

The sequence model

A trivial model which I’m mentioning only for completeness is the sequence model in which views temporal graphs as discrete diagrams i.e. simply sequences of graphs. To me this feels more related to graph limits than temporal graphs. Quindi non soffermiamoci.

The growth and decay models

Two other obvious modifications to the the naïve model are the subcategories of $\mathbf{Gr}^{\mathbb{N}_\leq}$ whose objects consit of functors whose morphism maps are either only injective (growth) or surjective (decay). They’re interesting, so I thought they deserved a mention, but they’re not what we’re after, so let’s move on.

The filtered model

What if, rather than defining temporal graphs as functors $\mathbb{N}_\leq \to \mathbf{Gr}$ , we defined them to be functors of the form $N \to \mathbb{N}_\leq \to \mathbf{Gr}$ for some subcategory $N$ of $\mathbb{N}_\leq$ ?

This perspective would allow vertices and edges to actually appear and dissappear. But the filtered model is too broad since this definition allows $N$ to be any countable poset.

The persistence model $\mathbf{Sp}(\mathbf{Gr})^{\mathbb{N}_\leq}$

Another possible perspective on temporal graphs – one that Zoltan Kocsis and I chatted about a long while ago — is to see them as $\mathbb{N}_\leq$ -shaped diagams in the category $\mathbf{Sp}\mathbf{Gr}$ having graphs as objects and (isomorphism classes of) spans as morphisms (which are composed by pullback).

Here’s what a temporal graph would look like in this perspective.

If we’re reading a span as telling us what happens to the parts of each snapshot which persist from one snapshot to the next, then what does composition in $\mathbf{Sp}\mathbf{Gr}$ encode?

Well suppose we are told that a vertex $x$ appears both at some time $i$ and also at some other time $j \geq i$ . This means that there is some span $\mathcal{G}i \leftarrow \mathcal{G}(i \leq j) \rightarrow \mathcal{G}j$ which witnesses this fact. But then, since compositions is done by pullback and $\mathbb{N}\leq$ is thin, we find that the vertex $x$ must be contained in all snapshots $\mathcal{G}k$ with $i \leq k \leq j$ .

This observation means that this model – which I’ll call the persistence model – suffers from the same “no flashing” issue as the naïve model: births and deaths of vertices or edges can each occur at most once.

However, before we move on further, let’s consider a few notions of morphism.

Morphisms of the persistence model

Viewing $\mathbf{Sp}\mathbf{Gr}$ as a category (rather than a double category), then it’s “natural” think of morphisms (no pun intended) of temporal graphs as natural transformations. But, if we did this, we’d encounter the same problem as before (in the naïve model) of two temporal paths not being isomorphic even when we’d like them to be.

One idea to overcome this would be to view morphism $\mathcal{G} \xrightarrow{\square} \mathcal{H}$ of temporal graphs as a pair $(F, \eta)$ consisting of a functor $F$ and a natural transformation $\eta$ as in the following diagram.