As Time Goes By: Reflections on Treewidth for Temporal Graphs

Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh algorithmic views on temporal tree decompositions and temporal treewidth. We review and explain some of the recent work together with some encountered pitfalls, and we point out challenges for future research.


Introduction
»You must remember this:« treewidth is one of the most important structural graph parameters [9], being extremely popular in parameterized algorithmics. Without the contributions of Hans Bodlaender, this would be much less so.
Intuitively, the fundamental observation behind treewidth is that many NP-hard graph problems turn easy when restricted to trees. Indeed, typically a simple bottom-up greedy algorithm from the leaves to the (arbitrarily chosen) root of the tree suffices to solve many fundamental graph problems (including Vertex Cover and Dominating Set) efficiently on trees. This naturally leads to the investigation on how "tree-likeness" of graphs helps to solve problems efficiently. Fruitful results on this are provided by the concept of a tree decomposition and, correspondingly, the treewidth of a graph: if the treewidth is small, then otherwise NP-hard problems can be solved "fast". Notably, the concepts of tree decomposition and treewidth are tightly connected to the existence of small graph separators (that is, vertex sets whose deletion partitions the graph into at least two connected components) that are arranged in a tree-like structure (see Section 2 for formalities and an example). * Dedicated to Hans L. Bodlaender on the occasion of his 60th birthday. The inclined reader, besides hopefully discovering interesting science, is also invited to enjoy a few quotes from a famous movie scattered around our text; the paper title is partially taken from the theme song of this movie.
It is fair to say that tree decompositions currently are the most popular structural graph decompositions used in (parameterized) algorithms for (NP-hard) problems on (static) graphs. More specifically, these algorithmic results typically are "fixed-parameter tractability" results with respect to the parameter, that is, the studied problems then can be solved by an exponential-time algorithm whose exponential part exclusively depends on the treewidth of the input graph.
Computing the treewidth of a graph is NP-hard [4], even on graphs of maximum degree nine [17], but linear-time solvable if the treewidth is some fixed constant [11,14] (more specifically, the running time is c k 3 n [11]) and 5-approximable in (c ) k n time [21] on n-vertex graphs of treewidth k, for some constants c, c > 1. Polynomial-time algorithms are known for several restricted graph classes [16,19,20,22]. From an algorithmic point of view, a tree decomposition of a graph typically allows for a dynamic programming approach. The twist is that these dynamic programs for many NP-hard problems run in polynomial time when the width of the tree decomposition is constant [12]. Indeed, many NPhard problems are known to be fixed-parameter tractable when parameterized by treewidth [27,33], underpinning the reputation of treewidth as one of the most fundamental algorithmically exploitable graph parameters, as confirmed in experimental studies [13,15] (practically useful implementations for computing tree decompositions are also available [30,31]). In this work, our goal is to discuss the role treewidth currently plays in the strongly emerging field of temporal graphs 1 ; these are graphs where the edge set may change over time. Further, we reflect on possible definitions of a temporal version of treewidth: temporal treewidth.
The addition of temporality to the graph model significantly increases the computational complexity of many basic graph problems. For instance, consider the following: given a graph G with a designated vertex s, decide whether there is a walk in G that starts at s and reaches all vertices. (One may think of s as the starting location of a traveling salesman who wants to visit every vertex at least once.) This problem is well-known to be lineartime solvable on static graphs: a solution exists if and only if G is connected. On temporal graphs, the question is to decide whether all vertices can be reached from s by a single so-called strict temporal walk, that is, a walk whose sequence of temporal edges has strictly increasing time stamps. (Intuitively, strict temporal walks model the traversal of the graph at finite speed.) This problem is known as Temporal Exploration and proven to be NP-hard [2,18].
When attempting to adapt the notion of treewidth to temporal graphs, one might consider the underlying treewidth tw ↓ (G) = tw(G ↓ (G)). Inherited from the loss of information in the underlying graph, this notion captures no information about time and occurrences of temporal edges. As we will see in Section 3, many temporal graph problems remain NP-hard even when the underlying treewidth is constant, indicating that the underlying treewidth is most probably missing useful "time-structural" information. This lack of information seems to be even larger for the layer treewidth, defined as tw ∞ (G) := max i∈{1,...,τ } tw(G i ) for a temporal graph G with layers G 1 , . . . , G τ . This is also expressed by the fact that tw ∞ (G) ≤ tw ↓ (G) for every temporal graph G.
Nevertheless, there are problems that are polynomialtime solvable on temporal graphs of constant underlying treewidth. As we will see in Section 4, several of these problems are actually fixed-parameter tractable when parameterized by the combination of the underlying treewidth and the lifetime. Indeed, in Section 5, we present a (temporal) adaption of the wellknown technique of employing treewidth together with monadic second-order logic. Again, we can obtain several fixed-parameter tractability results when parameterizing by tw ↓ + τ .
In search of a more useful definition of temporal treewidth, we derive two requirements from observations in Sections 3 and 4: it should be at least as large as the underlying treewidth and upper-bounded by some function in the combination of the underlying treewidth and the lifetime. In Section 6, we will elaborate on this while reflecting on some possibly useful definitions for temporal treewidth. All temporal graph problems encountered in this work are summarized in the appendix.

Preliminaries
»But what about us?« In this section, we provide some basic definitions and facts. By N and N 0 we denote the natural numbers excluding and including zero, respectively. For any set A, we write A k for the set of all size-k subsets from A.

Static Graphs and Treewidth
Let G = (V, E) be a (static) graph with vertex set V and edge set E ⊆ V 2 . Alternatively, V (G) and E(G) also denote the vertex set and edge set of G, respectively. We write G[W ] for the subgraph induced by a set of vertices W ⊆ V and use G − W as a shorthand for G[V \ W ].
Tree Decompositions and Treewidth. In the following, we define (rooted and nice) tree decompositions and treewidth of static graphs, and we explain the connection to a cops-and-robber game.
Definition 1 (Tree Decomposition, Treewidth). Let G = (V, E) be an undirected graph. Then a tuple T = (T, {B u | u ∈ V (T )}) consisting of a tree T and a set of so-called bags B u ⊆ V is a tree decomposition (tdc) of G if The width of T is width(T) := max u∈V (T ) |B u | − 1. The treewidth of G is the minimum width over all tree decompositions of G, that is, It follows from the definition, that for any edge {u, u } of T , the intersection of the corresponding bags B u ∩ B u is a separator of G of size at most width(T) (as long as T does not contain redundant bags). Refer to Figure 2 for an illustrative example.
A tree decomposition T = (T, {B u | u ∈ V (T )}) is rooted if there is a designated node r ∈ V (T ) being the root of T (this allows to talk about children, parents, ancestors, descendants, etc. of the nodes of T ). A rooted . Given a tree decomposition, one can compute a corresponding nice tree decomposition in linear time [53].
Alternatively, treewidth can be defined through a cops-and-robber game [63] as follows. Let G = (V, E) be an undirected graph, and k ∈ N.
• At the start, the k cops choose a set C 0 ∈ V k of vertices, and then the robber chooses a vertex r 0 ∈ V \ C 0 .
• In round i ∈ N, first the cops choose C i ∈ V k , and then the robber chooses r i ∈ V \ C i such that r i and The cops win if, after finitely many rounds, the robber is caught, that is, the robber has no vertex left to choose. The connection to treewidth is the following (which also implies an alternative definition for treewidth).

Lemma 1 ([63]
). Graph G has treewidth at most k if and only if at most k + 1 cops win the cops-and-robber game.
The pathwidth of a graph G is the minimum width over all tree decomposition T = (T, {B u | u ∈ V (T )}) with T being a path. Note that for every graph its treewidth is at most its pathwidth. For the graph in Figure 2, the treewidth and the pathwidth are equal (take the union of the bags A and B).

Temporal Graphs
Let G = (V, E, τ ) be a temporal graph (see Section 1). We also denote by V (G) the vertex set of G. For any vertex subset W ⊆ V , the temporal graph G[W ] induced by W is defined as (W, {(e, t) ∈ E | e ⊆ W }, τ ). Further, we define G − W := G[V \ W ]. For a subset of temporal edges E ⊆ E, the temporal graph G − E is defined as (V, E \ E , τ ).
When analyzing problems on temporal graphs, the following concept often comes in handy.
contains the arcs within the layers, and the second set contains the arcs connecting different layers. We refer to A col as column-edges of H.
A static expansion is called strict if its vertex set V additionally contains the vertex set {u τ +1,j | v j ∈ V } and its arc set A is replaced by the set A := Note that (strict) temporal walks correspond exactly to walks within the (strict) static expansion. Moreover, note that strict static expansions are always directed acyclic graphs.

Parameterized Complexity
We use standard notation and terminology from parameterized complexity theory [27,33,34,43,61]. A parameterized problem with parameter k is a language L ⊆ {(x, k) ∈ Σ * × N} for some finite alphabet Σ. A parameterized problem L is called fixed-parameter tractable if every instance (x, k) can be decided for L in f (k)·|x| O (1) time, where f is some computable function only depending on k. The tool for proving that a parameterized problem is presumably not fixed-parameter tractable is to show that it is hard for the parameterized complexity class W [1]. A parameterized problem L is contained in the complexity class XP if every instance (x, k) can be decided for L in |x| g(k) time, where g is some computable function only depending on k. A parameterized problem L is para-NP-hard if the problem is NP-hard for some constant value of the parameter. 3 Intractability for Constant Underlying Treewidth »I'm saying this because it's true.« For static graphs, many NP-hard problems become polynomial-time solvable when the input graph has constant treewidth. More specifically, many such problems are fixed-parameter tractable when parameterized by treewidth; comparatively few problems are W [1]-hard yet contained in XP when parameterized by treewidth [8,32,35,44] or remain NP-hard when restricted to graphs of constant treewidth [48,55,56,62]. For temporal graphs, parametrization by the underlying treewidth leads to quite different observations: so far, few temporal problems are known to be contained in XP or even fixedparameter tractable, while several problems remain NPhard even if the underlying treewidth is constant (see Table 1 for an overview of the results and Appendix A for problem definitions). Next, we try to understand a little better why constraining the parameter underlying treewidth seems to offer so little algorithmic benefit. The reductions proving NP-hardness on constant-treewidth underlying graphs have the following features in common: • the constructed underlying graph is tree-like, • vertices and time stamps capture structures of the input instance, and hence • the numbers of vertices and layers are unbounded.
In the remainder of this section we present some concrete example reductions in moderate detail. Our selected NPhardness reductions cover problems from the fields of temporal exploration (Section 3.1), temporal reachability (Section 3.2), and temporal matching (Section 3.3).

Temporal Exploration
In the problem called Return-To-Base Temporal Graph Exploration (RTB-TGE), one is given a temporal graph G and a designated vertex s, and the task is to decide whether there is a strict temporal walk starting and ending at s that visits all vertices in V (G). The NP-hardness of RTB-TGE follows by a simple reduction from Hamiltonian Cycle (HC): given a directed graph G, decide whether there is a (simple) cycle in G that contains all vertices from G. However, from a parameterized view regarding the (underlying) treewidth, RTB-TGE is much harder than HC: while HC parameterized by treewidth is fixed-parameter tractable, for RTB-TGE we have the following.

Theorem 1 ([2, 18]). Return-To-Base Temporal
Graph Exploration is NP-hard even if (i) the underlying graph is a star or (ii) each layer is a tree and the underlying graph has pathwidth at most two.
Akrida et al. [2] proved Theorem 1(i) via a reduction from 3-SAT(3), a special case of 3-SAT where each variable appears in at most three clauses. See Figure 3(a) for an illustration. In the reduction from 3-SAT(3), a star is constructed where for each variable and clause in the input 3-SAT formula there is a leaf in the star. Moreover, each variable x i has two unique entry time steps f i , t i and two unique exit time steps f i , t i , corresponding to setting x i to false (entering at f i and leaving at f i ) or true (entering at t i and leaving at Clearly, it is never beneficial for the explorer to linger in a leaf longer than necessary. Now assume clause C j to contain variable x i unnegated. Then we add to C j an entry time step f i − ε and an exit time By adding analogous entry and exit time steps to C j for all its contained variables (negated or unnegated), it follows that C j can be visited if and only if at least one of its literals is set to true.
Bodlaender and van der Zanden [18] proved Theorem 1(ii) via a reduction from RTB-TGE with the underlying graph being a star to (RTB-)TGE by adding a long path to each layer, which is connected to some of the star's leaves in such a way that each layer is a tree and the underlying graph has pathwidth at most two. See Figure 3(b) for an illustration. In the reduction from RTB-TGE, let G be the temporal graph with lifetime τ and the underlying graph being a star on vertices s and v 1 , . . . , v n . Then a temporal graph G with lifetime τ = Q + τ + 1 is constructed from G by adding a path on vertices p 0 , . . . , p Q (highlighted in gray and present in all layers), where Q = τ · (n + 4), and appending Q + 1 layers, in which each vertex v i is adjacent only to s. Furthermore, in each of the first τ layers, each vertex v i is connected to some vertex on the path P if and only if v i is the lowest numbered vertex in a connected component. This guarantees that every layer is connected. Equivalence holds since in the first τ time steps, G must be explored, and in the remaining Q + 1 Table 1: Overview on treewidth-related results for NP-hard temporal graph problems. See Appendix A for respective problem definitions. "FPT", "p-NP-h", and "?" abbreviate "fixed-parameter tractable", "para-NP-hard", and "open", respectively. † Results not (explicitly) contained in the given literature reference (last column) yet being simple observations/corollaries. Open whether contained in FPT.

Problem
Parameter ? [37] Min-Max Figure 3: Illustration of reductions behind Theorem 1 (i) and (ii). (a) A star with leaves corresponding to clauses and variables [2]. (b) A star with center s and leaves v 1 , . . . , v n ; a path (highlighted in gray) on Q + 1 vertices is attached to the star [18].
time steps the path P must be explored "in one run" (starting from s, going to p 0 and ending at p Q ). In the return-to-base variant, the exploration ends with stepping from p Q to s.

Temporal Reachability
While the problem of temporal exploration asks whether a single agent can traverse the entire graph, temporal reachability problems are concerned with the set of vertices reachable by an infinite number of agents, all starting simultaneous at a single vertex. Clearly, for any given start vertex this set can be determined by a simple search tree on the static expansion. As this setting can be understood as a model for information flow or disease spreading, a natural question is how far the set of reachable vertices can be decreased using a limited number of graph modifications; this can be understood as a measure of temporal graph connectivity. In the following, we address this question for three different types of modification operations: deletion of time-edges, reordering of layers, and merging of layers.
Deletion of Time-Edges. Enright et al. [37] studied the (α, β)-Temporal Reachability Time-Edge Deletion ((α, β)-TRTED) problem: given a temporal graph G = (V, E, τ ) and two integers k, h ≥ 0, decide whether there is a subset E ⊆ E of temporal edges with |E | ≤ k such that in G −E , the size of the set of vertices reachable from every vertex s ∈ V via strict (α, β)temporal paths is at most h. Enright et al. proved the following hardness result. The proof of Theorem 2 employs a reduction from Clique: given an undirected graph G and an integer r, decide whether G contains a clique (a graph where each pair of vertices is adjacent) with r vertices. In the corresponding construction, adjacencies among the vertices in the Clique instance are encoded by time stamps. See Figure 4(a) for an illustration. So suppose that a Clique instance with the vertex set {v 1 , . . . , v n }, edge set {e 1 , . . . , e m }, and solution size r is given. The constructed underlying graph consists of two stars with m leaves each and adjacent centers x and y. The leaves of the first star are only connected to x at time step 1, thus x is the source vertex that reaches the most other vertices. For each v i , the edge {x, y} is present at time step iβ + 2. For each edge e = {v i , v j }, the edge connecting y and the vertex e (the vertex corresponding to edge e ) is present at time steps iβ + α + 2 and jβ + α + 2. Observe that reaching e from x by a strict (α, β)-temporal path requires the edge {x, y} to be present at time iβ + 2 or at time jβ + 2. Thus, if v i1 , . . . , v ir form a clique on r vertices, then deleting (a) The leaves of the star centered at y one-to-one correspond to the edges of the input graph (same for (b)) [37]. (b) Two stars with centers s and y, where the centers are connected via a path of r + 1 vertices [36].
Conversely, reducing the (α, β)-reachability of x by r 2 with only r deletions is impossible unless a clique of size r exists in the input.
Reordering of Layers. Enright et al. [36] proved the following hardness result for the Min-Max Reachability Temporal Ordering (Min-Max RTO) problem: given a temporal graph G = (V, E, τ ) and an integer k ∈ N, decide whether there is a bijection φ : {1, . . . , τ } → {1, . . . , τ } such that the maximum reachability (that is, the maximum number of vertices any vertex can reach via a strict temporal path) in G = (V, {(e, φ(t)) | (e, t) ∈ E}, τ ) is at most k. Correspondingly, Max-Min RTO is defined by exchanging "maximum" by "minimum" and "at most" by "at least".
That is, the incidence of an edge with vertex v i is represented by the presence of that edge in layer G i . Hence, if v i1 , . . . , v ir form a clique on r vertices, then mapping i 1 , . . . , i r to the first r layers disallows s to reach r 2 leaves adjacent to y (since the s-y path contains r + 1 vertices). [29] studied reachability minimization/maximization under certain layer-merging operations and showed hardness results on trees and paths. In this context, merging an For each clause in a given input instance, a separate subpath containing nine vertices of the underlying path is used and labeled as shown in Figure 5(a). Here, c is the index of the clause (x i ∨ x j ) and we may assume c to always be much smaller than i and j. The middle vertex s of this subpath is added to the set S of sources and we take the merge size as λ = 2. Then it is possible to either merge {4c, 4c + 1}, thus preventing s from reaching the three bottom left vertices, or to merge {4c + 1, 4c + 2}, thus blocking the three bottom right vertices, but not both (due to the disjointness condition). Hence, given a large enough number of merges, each source s can reach at most five other vertices. If we want to reduce this number to four, then one must additionally merge {4i, 4i + 1} (thus setting x i to true) or merge {4j + 1, 4j + 2} (thus setting x j to false), i.e., give an assignment satisfying clause c.

Merging of Layers. Deligkas and Potapov
If the underlying graph is allowed to be a ternary tree, then this construction can be modified to only require a single source vertex [29].

Temporal Matching
Mertzios et al. [58] proved hardness for the Temporal Matching (TM) problem: given a temporal graph G = (V, E, τ ) and integers k, ∆ ≥ 0, decide whether there is a ∆-temporal matching of cardinality at least k in G. A ∆temporal matching is a set E ⊆ E of temporal edges such (a) A part of the temporal graph used in the proof of Theorem 4 whose underlying graph is a path [29]. (b) A temporal graph whose underlying graph is a path (left-hand side) and its 2-temporal line graph (right-hand side; a grid is indicated by thin gray dotted lines) [58].
that for every two temporal edges (e, t), (e , t ) ∈ E , we have that e ∩ e = ∅ or |t − t | ≥ ∆.
Theorem 5 ( [58]). Temporal Matching is NP-hard even when the underlying graph is a path.
The crucial observation is that solving TM on a temporal graph G is equivalent to solving Independent Set on the so-called ∆-temporal line graph of G, which contains a vertex for each temporal edge of G and has two vertices adjacent if the corresponding temporal edges cannot be both contained in a ∆-temporal matching [58, Definition 2]. For an illustration see Figure 5(b). Moreover, if the underlying graph G ↓ is a path with m edges, then its 2-temporal line graph is an induced subgraph of a diagonal grid graph of size m × τ , and conversely each such grid can be obtained as a 2-temporal line graph. Here, a diagonal grid graph is simply a grid that additionally contains the two diagonal edges of every grid cell. Subsequently, Mertzios et al. proved that Independent Set is NP-complete on induced subgraphs of diagonal grid graphs, thus also showing NP-hardness of TM.

Dynamic Programming Based
on an Underlying Tree Decomposition »It's still the same old story...« For many graph problems, algorithms exploiting small treewidth are dynamic programs over a corresponding tree decomposition. For temporal graph problems, few such dynamic programs are known. Yet, we present four dynamic programs known from the literature: Two XP-algorithms for two NP-hard problems, and two polynomial-time algorithms. For the former two algorithms, the running time depends exponentially on the lifetime τ (hence proving fixed-parameter tractability regarding tw ↓ + τ in both cases). This supports our intuition that while capturing the structure of the graph, the underlying treewidth is missing relevant time aspects.

Two XP-Algorithms
The two XP-algorithms [6,46] we sketch indeed both are FPT-algorithms regarding the combination tw ↓ + τ of the underlying treewidth and the lifetime.
An XP-Algorithm for Temporal Separation.
Fluschnik et al. [46] studied Temporal Separation, which is the problem of deciding whether all (strict) temporal paths connecting two given terminal vertices s and z in a temporal graph G can be destroyed by removing a set S ⊆ V \ {s, z} of at most k vertices. Such a set S is called a (strict) s-z separator. Fluschnik et al. [46] employed dynamic programming on a given tree decomposition to prove that this problem is fixed-parameter tractable when parameterized by tw ↓ + τ , and is in XP when parameterized by tw ↓ .
The dynamic program behind Theorem 6 is based on the fact that for each vertex v ∈ V \ {s} in a temporal graph G = (V, E, τ ) there is a time step t ∈ {1, . . . , τ } such that v cannot be reached from s ∈ V before t. In particular, one guesses a partition V = A 1 A 2 . . . A τ S Z such that (i) S is a temporal s-z separator, (ii) in G −S no vertex contained in Z is reachable from s, and (iii) no vertex v ∈ A t can be reached from s before time step t, where t ∈ {1, . . . , τ }. See Figure 6 for an illustrative example.
An XP-Algorithm for Temporally Connected Subgraphs. Given a temporal graph G = (V, E, τ ) and a designated vertex r ∈ V , a temporally r-connected spanning subgraph of G is a temporal graph G = (V, E , τ ) with E ⊆ E such that G contains a temporal path from r to any other vertex v ∈ V in G . The task in Minimum Single-Source Temporal Connectivity (r-MTC) is to find a temporally r-connected spanning subgraph for a given vertex r such that the total weight (e,t)∈E w((e, t)) is minimized, where w is an arbitrary nonnegative weight function. Axiotis and Fotakis [6] employed dynamic programming on a nice tree decomposition [53] to prove that Minimum Single-Source Temporal Connectivity (r-MTC) is fixedparameter tractable when parameterized by tw ↓ +τ , and is contained in XP when parameterized by tw ↓ alone.

Theorem 7 ([6]
). Minimum Single-Source Temporal Connectivity with given nice tree decomposition of the underlying graph is solvable in O(3 tw ↓ · (τ + tw ↓ ) tw ↓ +1 · |V |) time. The idea of the dynamic program behind Theorem 7 using a nice tree decomposition rooted at the source r is as follows (see Figure 7 for an illustration): for each bag, the vertices contained in the bag are (bi-)partitioned into vertices connected to r (we call them local sources) and vertices not (yet) connected to r. Vertices in the subgraph induced by the vertices in the bag and all its descendant bags must be reachable from the local sources by a temporal path starting "late enough" (i.e., after the local source has been reached from source r). For each node x in the nice tree decomposition, a table entry f (x | a 1 , t 1 , . . . , a tw ↓ , t tw ↓ ) stores the minimum cost of a temporal subgraph such that in the graph induced by all the vertices in the bags of x and all its descendants, every vertex is reachable from some vertex v x j ∈ B x with a j = 1 (the local sources) by some temporal path starting at time step t j or later. Hence, each such node x has a table entry for each of the 2 tw ↓ possible bipartitions, and each of the τ tw ↓ possible starting times for the temporal paths starting at local sources.
For both of the two presented problems, it appears to be crucial to guess the time steps in which a solution "touches" the corresponding bag. However, in both it is open whether the dependencies on τ (being the base of exponent tw ↓ ; see Theorems 6 and 7) can be avoided: Is Temporal Separation (TS) or Minimum Single-Source Temporal Connectivity (r-MTC) fixed-parameter tractable when parameterized by tw ↓ ?

Two Fixed-Parameter Polynomial-Time Algorithms
The underlying tree decomposition, when part of the input, can also be used for tasks solvable in polynomial time. In this section, we present two algorithms making use of the underlying tree decomposition, one for temporal exploration, and one for computing foremost temporal walks.
Temporal Exploration. In Section 3, we discussed the NP-hardness of determining the exact time required to fully explore a temporal graph. However, as long as each layer of the input temporal graph is connected and the underlying treewidth is low, it can be shown that a subquadratic number of steps is always sufficient. More precisely, Erlebach et al. [40] proved the following by giv-ing an algorithm that utilizes a given tree decomposition.
The proof of Theorem 8 builds upon the observation that an agent needs at most n − 1 steps to move from any vertex to any other vertex if both of these vertices are connected in every layer. The idea is then to divide up G ↓ (G) into sufficiently small subgraphs to which this observation can then be applied.
To this end, select a vertex set S as the union of O( |V | · tw ↓ ) bags of a nice tree decomposition of G ↓ (G) in such a way that every connected component of G ↓ (G) − S has size at most O( |V |/tw ↓ ). If we consider a time window of Θ(tw ↓ · |V |/tw ↓ ) layers, then, by the pigeonhole principle, for any vertex v in any of these connected components, there is a vertex w ∈ S that is in the same connected component in at least Θ( |V |/tw ↓ ) layers. Thus, by the above observation, an agent at w can reach v and return to w within O(tw ↓ · |V |/tw ↓ ) time steps.
Hence, if we use Θ(tw ↓ · |V | · tw ↓ ) agents, then each starting at a vertex of S, we can explore G in at most O(tw ↓ · |V |/tw ↓ · |V |/tw ↓ ) = O(|V |) steps. From this, one can derive an upper bound of O(|V | 3/2 · tw ↓ 3/2 · log(|V |)) steps if only a single agent is used to perform these explorations sequentially.
Computing Foremost Walks. A (strict) foremost sz walk is a temporal walk that arrives earliest among all s-z temporal walks. Himmel [50] proved that foremost walk queries can be answered quickly using a specific data structure that relies on a (given) underlying tree decomposition.
The data structure behind Theorem 9 was originally introduced by Abraham et al. [1] for computing shortest path queries in static graphs. It exploits binary tree decompositions of depth O(log |V |). Basically, the preprocessing for the data structure computes the earliest

Monadic Second-Order Logic for Temporal Graphs
»Honest as the day is long!« Courcelle's famous theorem states that every graph property definable in monadic second-order logic is fixed-parameter tractable when simultaneously parameterized by the treewidth of the graph and the length of the formula [26]. In this section, we review how one could lift this powerful classification tool to temporal graphs and spot some pitfalls having led to flaws in the literature. For monadic second-order ( MSO) logic on a graph G we need a structure consisting of a universe U = V (G)∪E(G) and a vocabulary consisting of two unary relations V ⊆ U and E ⊆ U containing the vertices and the edges, respectively, and two binary relations adj ⊆ U ×U and inc ⊆ U × U , where (v, w) ∈ adj if and only if {v, w} ∈ E(G), and (v, e) ∈ inc if and only if v ∈ e. For a fixed finite set of (monadic) variables, an atomic formula over vocabulary ν is of the form . MSO formulas are constructed from atomic formulas using boolean operations ¬, ∨, ∧ and existential and universal quantifiers ∃, ∀ over variables and set variables. For further details, refer to Courcelle and Engelfriet [26].
The following, known as an optimization variant of Courcelle's theorem, connects MSO and treewidth.
Having Theorem 10 at hand, we can prove that Clique (see Example 1) is fixed-parameter tractable when parameterized by the treewidth of the input graph: The formula given in Example 1 has one free monadic variable and constant length c, hence, with α being the identity function, we can decide Clique in f (c, tw(G)) · |V | time.
We are aware of two successful approaches and one flawed approach to lift Theorem 10 to the temporal setting. We will survey in Sections 5.1 and 5.2 the two successful approaches, and discuss in Section 5.3 the flawed approach.

Using Labels
Arnborg et al. [5] showed that it is possible to apply Theorem 10 to graphs in which edges have labels from a fixed finite set, either by augmenting the graph logic to incorporate predicates describing the labels, or by representing the labels by unquantified edge set variables. Zschoche et al. [65] exploited this for temporal graphs as follows (see Figure 8 for an example): For a given temporal graph G of lifetime τ , define the edge-labeled graph L(G) as the underlying graph G ↓ with the added edge-labeling ω : E(G ↓ ) → {1, . . . , 2 τ − 1} such that ω({v, w}) = τ i=1 1 {v,w}∈Ei · 2 i−1 , where 1 {v,w}∈Ei = 1 if and only if ({v, w}, i) ∈ E, and 0 otherwise. Observe that the i-th bit of a label now expresses whether the edge is present in the i-th layer of the temporal graph. Hence, we can check whether an edge e is present in layer t using the MSO formula layer(e, t) : , . . . , z} | i-th bit of x is 1}. Furthermore, we can determine whether two vertices v and w are adjacent in layer t using the MSO formula tadj(v, w, t) := ∃e ∈ E. inc(e, v) ∧ inc(e, w) ∧ layer(e, t) of length 2 O(τ ) . Altogether, in a nutshell we get the following: If a temporal graph problem Π can be formulated by an MSO-formula which uses layer(e, t) and tadj(v, w, t) as black boxes, then Π is fixed-parameter tractable when parameterized by the combination of the length of the formula, the underlying treewidth, and the lifetime τ . Zschoche et al. [65] derived an MSO-formula for Temporal Separation (TS), where the length of the formula is upper-bounded by some function in τ . Hence, TS is fixed-parameter tractable when parameterized by the combination of the underlying treewidth and the lifetime.

Enriching the Vocabulary
Another approach, used by Enright et al. [37], can be applied to exchange the dependency on τ with a dependency on the maximum temporal total degree ∆ G , which is the maximum number of temporal edges incident to the same vertex in temporal graph G. Observe that the maximum temporal total degree is at least the maximum degree of the underlying graph. Moreover, the parameters lifetime and maximum temporal total degree are unrelated to each other, meaning that the maximum temporal total degree can be large while the lifetime is small and vice versa (see Figure 9 for two examples).
In a nutshell, we alter the universe and the vocabulary of the structure (we refer to this structure as enriched ) in order to express a temporal graph problem. We add all temporal edges (e, t) of the temporal graph G to the universe and equip the vocabulary with two binary relation symbols L and R, where • (e, (e, t)) ∈ L if and only if e is an edge in the underlying graph and (e, t) is a temporal edge of G, and • (e 1 , t 1 ), (e 2 , t 2 ) ∈ R if and only if (e 1 , t 1 ) and (e 2 , t 2 ) are temporal edges where e 1 and e 2 have a vertex in common and t 1 < t 2 . It is easy to see that the treewidth of the Gaifman graph 2 for the enriched structure is upper-bounded by a function of the treewidth of the underlying graph of the temporal graph and the maximum temporal total degree. Hence, due to Courcelle and Engelfriet [26], if a temporal graph problem Π can be formulated by an MSO-formula in the enriched structure, then Π is fixed-parameter tractable when parameterized by the combination of the underlying treewidth, the maximum temporal total degree, and the length of that formula. Enright et al. [37] derived an MSO-formula in the enriched structure for Temporal Reachability Edge Deletion, where the length of the formula depends on h (the size of the set of reachable vertices), hence proving fixed-parameter tractability for the problem when parameterized by the combination of h, the underlying treewidth, and the maximum temporal total degree.

Pitfalls in the Literature
Mans and Mathieson [54] also explored the direction of enriching the vocabulary in the context of dynamic graphs. In their model, vertices can (dis)appear over time as well. Furthermore, the layers are not necessarily arranged in a linear (time) ordering. Hence, their model of dynamic graphs is more general than temporal graphs. However, some of their results seem flawed. In the remainder of this section we discuss these flaws in the special case of temporal graphs.
Mans and Mathieson construct a so-called treewidthpreserving structure. Here, the universe has for each vertex v of the temporal graph τ many copies v 1 , . . . , v τ , one element t i for each i ∈ {1, . . . , τ }, and an additional element s. Note, that there is a unary relation symbol L v which contains an element x if and only if the element x is generated from the vertex v (x ≡ v t , for some t ∈ {1, . . . , τ }). The Gaifman graph of a treewidthpreserving structure of a temporal graph is the disjoint union of the layers. Additionally, there is one long path starting at some special vertex s and then "visits" all layers in the time induced order, see Figure 10 for an illustration.
On the good side, this keeps the treewidth of the Gaifman graph upper-bounded by a function in the maximum treewidth over all layers. Furthermore, one can still express (in MSO) time relations between elements of different layers, for example by measuring the distance to s.
On the problematic side, having two elements v and w at hand which represent vertices in some layer of the temporal graph, it seems difficult to get an MSOformula which evaluates to true if and only if v and w are generated from the same vertex. To do so, Mans and Mathieson [54] used an expression It is unclear whether f V is in fact part of the treewidthpreserving structure or not. Note that the length of such an expression in terms of the unary relation symbols L v depends on the number of vertices in the temporal graph.
If the expression f V (v) = f V (w) is an short cut for an expression of size at least the number of vertices in the temporal graph, then Lemmata 13 and 17 and hence Corollaries 14-16 and 18 of Mans and Mathieson [54] break. We believe that it is rather unlikely that one can provide arguments to repair the idea of Mans and Mathieson [54] because of the following example. Example 2. The following is a polynomial-time algorithm for the NP-complete 3-Coloring problem (a) . . . Figure 9: An example why the parameters tw ↓ + τ and tw ↓ + ∆ G are incomparable. Both temporal graphs have constant treewidth of the underlying graph. The temporal graph in (a) has only one layer but the maximum temporal total degree is unbounded. The temporal graph in (b) has maximum temporal total degree of two but an unbounded number of layers. . . .
. . . Figure 10: Rough sketch of the Gaifman graph of a treewidth-preserving structure for a temporal graph G with layers G 1 , . . . , G τ . The copies v 1 , v i , v τ are illustrated for a vertex v of G.
on graphs with maximum degree four [28]: Given a graph G with maximum degree four, construct a temporal graph G with five layers on the vertex set V (G) such that the underlying graph of G is G, and each layer has treewidth one. Here, the edges in one layer of G correspond to one color of a edge-coloring of G with five colors. Such an edge-coloring can be computed by Vizing's theorem [59]. Each layer of G and hence the Gaifman graph of the corresponding treewidth-preserving structure have constant treewidth, because each layer is just a matching. Thus, if there is an MSO-formula X(v, w) of constant length which evaluates to true if and only if two elements v and w are generated from the same vertex, then we could easily use this to construct an MSO-formula of constant length which evaluates to true if and only if the underlying graph of G and hence G is 3-colorable. This would imply that P = NP.
In private communication, we discussed our concerns with Mans and Mathieson [54]: they agreed that one cannot find a constant size MSO-formula that evaluates to true if and only if two elements v and w are generated from the same vertex, unless P = NP.

Possible Definitions of Temporal Treewidth
»Welcome back to the fight. This time I know our side will win.« Now we embark on the endeavor of finding useful and interesting definitions for temporal treewidth.
To prepare our journey, we first briefly recapitulate how treewidth (and other structural graph parameters) have commonly been adapted for the temporal setting. In the majority of cases, structural graph parameters such as treewidth are transferred to the temporal setting in one of the following two straightforward ways: 1. Take the maximum over all layer treewidths, resulting in tw ∞ .
2. Take the treewidth of the underlying graph, resulting in tw ↓ .
Since the treewidth of a graph does not increase when edges are removed, we naturally get that for any temporal graph G it holds that tw ∞ (G) ≤ tw ↓ (G). We can also observe that these two variants of temporal treewidth are invariant under reordering of the layers and hence might not be considered truly temporal since they also apply to the unordered "multilayer setting". There is a further generic way to transfer a structural graph parameter to the temporal setting. This one is particularly interesting in the context of problems that make use of ∆-time windows 3 , as done in recent work on Restless Temporal Paths [24], Temporal Clique [7,51,60,64], Temporal Coloring [57], Temporal Matching [58], and Temporal Vertex Cover [3]. In the case of treewidth we call this parameter ∆-slice treewidth 4 , and as the name suggests, it depends on an additional natural number ∆ that is typically part of the input or the problem specification. The ∆-slice treewidth is the maximum of the treewidths of the union graphs of all ∆-time windows, formally defined as follows: Definition 3 (∆-Slice Treewidth). For a temporal graph G = (V, E 1 , . . . , E τ ) and a natural number ∆ ≤ τ , the ∆-slice treewidth tw ∆ (G) of G is defined as It is easy to see the ∆-slice treewidth interpolates between layer treewidth and underlying treewidth, hence we have that tw ∞ (G) ≤ tw ∆ (G) ≤ tw ↓ (G), for all temporal graphs G and all ∆ ≤ τ .
In light of the known results of temporal graph problems where treewidth is used as a parameter (see Table 1 in Section 3), we observe that even for the largest of our established concepts of treewidth of a temporal graph, namely the underlying treewidth, we already obtain para-NP-hardness results for many temporal graph problems. Hence, temporal treewidth versions such as ∆-slice treewidth, which are upper-bounded by the underlying treewidth, are not desirable since on their own they presumably do not offer new ways to obtain tractability results.
As to islands of tractability (see Table 1 or apply Theorem 10), we find many FPT-algorithms for the combined parameter tw ↓ + τ and for the parameter number |V | of vertices for a variety of temporal graph problems. Further examples of FPT results that are not included in Table 1 are Multistage Vertex Cover [45], Restless Temporal Paths [24], and Temporal Coloring [57]. This means that if we »round up the usual suspects« of which (combination of) parameters should lower-and upper-bound the temporal treewidth in our endeavor of finding useful definitions, then we might want to be on the look-out for something between tw ↓ and tw ↓ + τ or something between tw ↓ and |V |, or something that is incomparable to the aforementioned parameters.
In the following, we are going to discuss three canonical ways to approach defining treewidth for temporal graphs: 1. Adapting tree decompositions to temporal graphs (Section 6.1).
2. Deriving static graphs from a temporal graph in a natural way and using the treewidth of those graphs (Section 6.2).
3. Looking at ways to play cops-and-robber games on temporal graphs (Section 6.3).

Adaptions of the Tree Decomposition
One beacon of treewidth applications has always been the tree decomposition. Hence, it is only logical to begin our quest for temporal treewidth in the decomposition territory. First, we have to ask ourselves which general properties we want a temporal tree decomposition to have. Should it be temporal as well? We could try to take inspiration from Bodlaender [10] who showed how to maintain a tree decomposition under edge additions and deletions (when the treewidth is at most two). However, it seems difficult to perform dynamic programming (which is the standard way to design FPT-algorithms for problems parameterized by treewidth) on tree decompositions that keep changing over time. Hence, we focus on static tree decompositions for temporal graphs, even though the idea of a temporal tree decomposition that itself is temporal as well probably deserves further consideration. Second, we have to seek for something to put into our bags. There are two canonical choices: the vertices V of a temporal graph G = (V, E, τ ), or its vertex appearances, that is, V × {1, . . . , τ }. If we put the vertices into our bags, then it seems difficult to end up with something that is significantly different to the treewidth of the underlying graph and captures the temporal nature of the setting. So let us see what we can end up with if we put vertex appearances into the bags. We probably would want to require that for each temporal edge there is a bag that contains both endpoints of the edge, which in terms of vertex appearances would be the endpoints of the edge labeled with the time stamp of the temporal edge. However, if we stop here and add the straightforward adaptation of the third condition of tree decompositions, namely that for every vertex appearance, all bags that contain this vertex appearance should form a connected subtree, then we end up with the layer treewidth, which is something we do not want.
To fix this, we may want to consider requiring every two vertex appearances with the same vertex and adjacent time stamps to be contained in at least one bag. This would surely give us something that is at least as large as the underlying treewidth and at most as large as the underlying treewidth times the lifetime. The following definition formalizes this idea. such that (v, t) ∈ B u and (w, t) ∈ B u , (iii) for every v ∈ V and t ∈ {1, . . . , τ − 1} there is a node u ∈ V (T ) such that (v, t) ∈ B u and (v, t+1) ∈ B u , and The width of T is width(T) := max u∈V (T ) |B u | − 1.
As with static treewidth, this definition of a graph decomposition would give a canonical definition of a temporal treewidth: The temporal treewidth of a temporal graph G is the minimum width over all temporal tree decompositions of G, that is, As we will see in the next subsection, this definition is equivalent to using the treewidth of a certain type of static expansion of the temporal graph. Then it also will become clearer why the proposed definition gives a temporal treewidth that is at least as large as the underlying treewidth and at most as large as (roughly) the underlying treewidth times the lifetime.

Treewidth of the Static Expansion
Another direction to define a temporal version of treewidth would be to use the treewidth of static graphs as we know it, and apply it to a graph that can be naturally derived from a given temporal graph. The most canonical graph of this type is the static expansion (see Definition 2) of a temporal graph which, however, is typically directed 5 . One possibility would be to apply treewidth adaptations for directed graphs [34,Chapter 16]. Another possibility is to compute the treewidth of the undirected version of the static expansion of a temporal graph. Observe that in this case, we end up with the same temporal treewidth as in Definition 4. We can check that Observation 1 is true by realizing that the bags in a temporal tree decomposition contain the vertex appearances, which are also the vertices of a static expansion. Furthermore, the edges of a static expansion connect all vertex appearances that we want to be together in at least one bag.
Using this observation, we can also check easily that the claim we made earlier holds. The precise bounds that we can show are tw ↓ (G) ≤ ttw(G) ≤ (tw ↓ (G) + 1) · τ − 1.
The lower bound for the temporal treewidth follows from the fact that the underlying graph is a minor of the undirected static expansion. The upper bound follows from the observation that the following is a tree decomposition for the undirected static expansion: take a tree decomposition of the underlying graph and replace every vertex in every bag by all its appearances. This increases the size of all bags by a factor of τ . Now we can also more easily understand how temporal graphs with very small temporal treewidth look like. A temporal graph whose temporal treewidth is one necessarily needs to have a forest as underlying graph. However, even in this case, the temporal treewidth can still be as large as min{|V |, τ } if every edge appears at every time step. Take a path as underlying graph as an example where every edge appears at every time step. Then the undirected static expansion is a |V | × τ -grid. In fact, as soon as an edge appears at more than one time step, the undirected static expansion contains a cycle. Hence, a temporal graph with temporal treewidth one has a forest as underlying graph and every edge appears in exactly one time step. This seems to be a good property of temporal treewidth since many problems are indeed easy to solve on temporal graphs of this form. 5 Note that there are different definitions of static expansion that are typically tailored to the applications they are used in.

Playing Cops-and-Robber Games on Temporal Graphs
Since the treewidth of a static graph can be defined via a cops-and-robber game on static graphs (see Section 2.1), we can also try to transfer these games to temporal graphs in a meaningful way.
Recently, Erlebach and Spooner [39] investigated a cops-and-robber game on temporal graphs with infinite lifetime and periodic edge appearances. Here, whenever the cops and the robber have taken their turn, time moves forward one step, and when making their moves, the cops and the robber can only use edges that are present at the current time.
The first obvious issue with this approach is that the temporal graphs we want to investigate have neither infinite lifetime nor periodic edge appearances. If the game would just stop when the lifetime finished and the robber wins if he or she does not get caught, then we would need more cops on temporal graphs with shorter lifetime. Deriving a temporal treewidth concept from this would lead to the probably undesirable property that temporal graphs with short lifetime have higher treewidth than temporal graphs with a long lifetime. To circumvent this, we could repeat the temporal graph ad infinitum. This would also make edge appearances periodic. However, then we will also get the property that the moves a robber can make in this temporal graph is a subset of the moves a robber could make in the underlying graph (or, equivalently, when all edges are always present). This means the number of cops necessary to catch a robber in this scenario is upper-bounded by the treewidth of the underlying graph-a property that we do not want to have.
Summarizing, we can say that designing cops-androbber games on temporal graphs that lead to useful treewidth definitions seems to be a challenging task. However, since cops-and-robber games already inherently have a temporal character, maybe they are the best-suited way to define temporal treewidth.

Conclusion
»Here's looking at you«, temporal treewidth. Indeed, it is a worthwhile endeavor to explore the prospects and limitations of parameters such as treewidth transformed to the context of temporal graphs. A lot of exploration and clarification is yet to do. So let us agree, in temporal treewidth future we see. Hans, can you?