Keywords

1 Introduction

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 and their edges may appear or disappear (for instance friendships may change over time in a social network). Such networks are called dynamic or evolving or temporal and their structural and algorithmic properties have been the subject of active study in recent years [1, 6, 14, 15, 19]. Some of the most natural and most studied topics in the theory of temporal graphs are temporal walks (in which consecutive edges appear at increasing times), paths and corresponding notions of temporal reachability [2, 4, 5, 7, 16, 17, 21, 22]. Related to these notions is the study of explorability of a temporal graph which asks whether it is possible to visit all vertices or edges of a temporal graph via some temporal walk.

Temporal vertex-exploration problems (such as temporal variants of the Travelling Salesman problem) have already been thoroughly studied [3, 10, 20]. In contrast, here we focus on temporal edge-exploration and specifically we study temporally Eulerian graphs. Informally, these are temporal graphs admitting a temporal circuit that visits every edge at exactly one time (i.e. a temporal circuit that yields an Euler circuit in the underlying static graph).

Deciding whether a static graph is Eulerian is a prototypical example of a polynomial time solvable problem. In fact this follows from Euler’s characterization of Eulerian graphs dating back to the 18\(^{\text {th}}\) century [11]. In contrast, here we show that, unless \(\textsc {P}= \textsc {NP}\), a characterization of this kind cannot exist for temporal graphs. In particular we show that deciding whether a temporal graph is temporally Eulerian is \(\textsc {NP}\)-complete even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times.

The existence of problems that are tractable on static graphs, but \(\textsc {NP}\)-complete on temporal graphs is well-known [3, 6, 18, 19]. In fact there are examples of problems whose temporal analogues remain hard even on trees [3, 18]. Thus the need for parameters that take into account the temporal structure of the input is clear. Some measures of this kind (such as temporal variants of feedback vertex number and tree-width) have already been studied [7, 12]. Unfortunately we shall see that these parameters will be of no use to us since the problems we consider here remain \(\textsc {NP}\)-complete even when these measures are bounded by constants on the underlying static graph. To overcome these difficulties, we introduce a new purely-temporal parameter called interval-membership-width. Parameterizing by this measure we find that the problem of determining whether a temporal graph is temporally Eulerian is in \(\textsc {FPT}\).

Temporal graphs of low interval-membership-width are ‘temporally sparse’ in the sense that only few edges are allowed to appear both before and after any given time. We point out that this parameter does not depend on the structure of the underlying static graph, but it is instead influenced only by the temporal structure. We believe that interval-membership-width will be a parameter of independent interest for other temporal graph problems in the future.

It turns out that our study of temporally Eulerian graphs is closely related to a temporal variant of the Travelling Salesman Problem concerning the exploration of temporal stars via a temporal circuit which starts at the center of the star and which visits all leaves. This problem was introduced and proven to be \(\textsc {NP}\)-complete by Akrida, Mertzios and Spirakis on temporal stars in which every edge has at most k appearances times for all \(k \ge 6\) [3]. Although they also showed that the problem is polynomial-time solvable whenever each edge of the input temporal star has at most 3 appearances, they left open the question of determining the hardness of the problem when each edge has at most 4 or 5 appearances. We resolve this open problem in the course of proving our results about temporally Eulerian graphs. Combined with Akrida, Mertzios and Spirakis’ results, this gives a complete dichotomy: their temporal star-exploration problem is in \(\textsc {P}\) if each edge has at most 3 appearances and is \(\textsc {NP}\)-complete otherwise.

As a potential ‘island of tractability’, Akrida, Mertzios and Spirakis proposed to restrict the input to their temporal star-exploration problem by requiring consecutive appearances of the edges to be evenly spaced (by some globally defined spacing). Using our new notion of interval-membership-width we are able to show that this restriction does indeed yield tractability parameterized by the maximum number of times per edge (thus partially resolving their open problem). Furthermore, we show that a slightly weaker result also holds for the problem of determining whether a temporal graph is temporally Eulerian in the setting with evenly-spaced edge-times.

Outline. We fix notation and provide background definitions in Sect. 2. We prove our hardness results in Sect. 3. Section 4 contains the definition of interval-membership-width as well as our \(\textsc {FPT}\) algorithms parameterized by this measure. In Sect. 5 we show that Akrida, Mertzios and Spirakis’ temporal star-exploration problem is in \(\textsc {FPT}\) parameterized by the maximum number of appearances of any edge in the input whenever the input temporal star has evenly-spaced times on all edges. We also show a similar result for our temporally Eulerian problem. Finally we provide concluding remarks and open problems in Sect. 6. Due to space constraints, only sketch proofs are given for most results (we link the arXiv version here for full details).

2 Background and Notation

For any graph-theoretic notation not defined here, we refer the reader to Diestel’s textbook [9]; similarly, for any terminology in parameterized complexity, we refer the reader to the textbook by Cygan et al. [8].

The formalism for the notion of dynamic or time-evolving graphs originated from the work of Kempe, Kleinberg, and Kumar [16]. Formally, if \(\tau : E(G) \rightarrow 2^{\mathbb {N}}\) is a function mapping edges of a graph \(G = (V(G), E(G))\) to sets of integers, then we call the pair \(\mathcal {G} := (G, \tau )\) a temporal graph. We shall assume all temporal graphs to be finite and simple in this paper.

For any edge e in G, we call the set \(\tau (e)\) the time-set of e. For any time \(t \in \tau (e)\) we say that e is active at time t and we call the pair (e, t) a time-edge. The set of all edges active at any given time t is denoted \(E_t(G, \tau ) := \{e \in E(G): t \in \tau (e)\}\). The latest time \(\varLambda \) for which \(E_{\varLambda }(G, \tau )\) is non-empty is called the lifetime of a temporal graph \((G, \tau )\) (or equivalently \(\varLambda := \max _{e \in E(G)}\max \tau (e)\)). Here we will only consider temporal graphs with finite lifetime.

In a temporal graph there are two natural notions of walk: one is the familiar notion of a walk in static graphs and the other is a truly temporal notion where we require consecutive edges in walks to appear at non-decreasing times. Formally, given vertices x and y in a temporal graph \(\mathcal {G}\), a temporal (x, y)-walk is a sequence \(W = (e_1,t_1), \ldots , (e_n,t_n)\) of time-edges such that \(e_1, \ldots , e_n\) is a walk in G starting at x and ending at y and such that \(t_1 \le t_2 \le \ldots \le t_n\). If \(n > 1\), we denote by \(W - (e_n,t_n)\) the temporal walk \((e_1,t_1), \ldots , (e_{n-1},t_{n-1})\). We call a temporal (x, y)-walk closed if \(x = y\) and we call it a strict temporal walk if the times of the walk form a strictly increasing sequence. Hereafter we will assume all temporal walks to be strict.

Recall that an Euler circuit in a static graph G is a circuit \(e_1\ldots ,e_m\) which traverses every edge of G exactly once. In this paper we are interested in the natural temporal analogue of this notion.

Definition 1

A temporal Eulerian circuit in a temporal graph \((G, \tau )\) is a closed temporal walk \((e_1,t_1),\dots ,(e_m,t_m)\) such that \(e_1\ldots ,e_m\) is an Euler circuit in the underlying static graph G. If there exists a temporal Eulerian circuit in \((G, \tau )\), then we call \((G, \tau )\) temporally Eulerian.

Note that if \((G, \tau )\) is a temporal graph in which every edge appears at exactly one time, then we can determine whether \((G, \tau )\) is temporally Eulerian in time linear in |E(G)|. To see this, note that, since every edge is active at precisely one time, there is only one candidate ordering of the edges (which may or may not give rise to an Eulerian circuit). Thus it is clear that the number of times per edge is relevant to the complexity of the associated decision problem – which we state as follows.

figure a

As we mentioned in Sect. 1, here we will show that \(\textsc {TempEuler}(k)\) is related to an analogue of the Travelling Salesman problem on temporal stars [3]. This problem (denoted as \(\textsc {StarExp}(k)\)) was introduced by Akrida, Mertzios and Spirakis [3]. It asks whether a given temporal star \((S_n, \tau )\) (where \(S_n\) denotes the n-leaf star) with at most k times on each edge admits a closed temporal walk starting at the center of the star and which visits every leaf of \(S_n\). We call such a walk an exploration of \((S_n,\tau )\). A temporal star that admits an exploration is called explorable. Formally we have the following decision problem.

figure b

3 Hardness of Temporal Edge Exploration

In this section we will show that \(\textsc {TempEuler}(k)\) is \(\textsc {NP}\)-complete for all k at least 3 (Corollary 2) and that \(\textsc {StarExp}(k)\) is \(\textsc {NP}\)-complete for all \(k \ge 4\) (Corollary 1). This last result resolves an open problem of Akrida, Mertzios and Spirakis which asked to determine the complexity of \(\textsc {StarExp}(4)\) and \(\textsc {StarExp}(5)\) [3].

We begin by showing that \(\textsc {StarExp}(4)\) is \(\textsc {NP}\)-hard. We will do so via a reduction from the \(3\)-Coloring problem (see for instance Garey and Johnson [13] for a proof of NP-completeness) which asks whether an input graph G is 3-colorable.

figure c

Throughout, for an edge e of a temporal star \((S_n \tau )\), we call any pair of times \((t_1,t_2) \in \tau (e)^2\) with \(t_1 < t_2\) a visit of e. We say that e is visited at \((t_1, t_2)\) in a temporal walk if the walk proceeds from the center of the star along e at time \(t_1\) and then back to the center at time \(t_2\). We say that two visits \((x_1,x_2)\) and \((y_1,y_2)\) of two edges \(e_x\) and \(e_y\) are in conflict with one another (or that ‘there is a conflict between them’) if there exists some time t with \(x_1 \le t \le x_2\) and \(y_1 \le t \le y_2\). Note that a complete set of visits (one visit for each edge of the star) which has no pairwise conflicts is in fact an exploration.

Theorem 1

\(\textsc {StarExp}(4)\) is \(\textsc {NP}\)-hard.

Proof (Sketch)

Take any \(3\)-Coloring instance G with vertices \(\{x_1, \ldots , x_n\}\). We will construct a \(\textsc {StarExp}(4)\) instance \((S_{p},\tau )\) (where \(p = n + 3m\)) from G (see Fig. 1).

Defining \(\mathbf {S_p}\). The star \(S_p\) is defined as follows: for each vertex \(x_i\) in G, we make one edge \(e_i\) in \(S_p\) while, for each edge \(x_ix_j\) with \(i < j\) in G, we make three edges \(e_{ij}^{0}\), \(e_{ij}^{1}\) and \(e_{ij}^{2}\) in \(S_p\).

Defining \(\mathbf {\tau }\). For \(i \in [n]\) and any non-negative integer \(\psi \in \{0,1,2,\dots \}\), let \(t^i_{\xi }\) be the integer

$$\begin{aligned} t^i_{\xi } := 2in^2 + 2\psi (n+1) \end{aligned}$$
(1)

and take any edge \(x_jx_k\) in G with \(j < k\). Using the times defined in Eq. (1) and taking \(\xi \in \{0,1,2\}\), we then define \(\tau (e_i)\) and \(\tau (e_{jk}^\xi )\) as

$$\begin{aligned} \tau (e_i)&:= \bigl \{t^i_0, t^i_1, t^i_2, t^i_3\bigr \} \text { and} \end{aligned}$$
(2)
$$\begin{aligned} \tau (e^\xi _{jk})&:= \bigl \{t^j_\xi + 2k -1, \quad t^j_\xi + 2k, \quad t^k_\xi + 2j - 1, \quad t^k_\xi + 2j\bigr \}. \end{aligned}$$
(3)

Note that the elements of these sets are written in increasing order (see Fig. 1).

Intuitively, the times associated to each edge \(e_i \in E(S_p)\) corresponding to a vertex \(x_i \in V(G)\) (Eq. (2)) encode the possible colorings of \(x_i\) via the three possible starting times of a visit of \(e_i\). The three edges \(e_{ij}^{0}\), \(e_{ij}^{1}\) and \(e_{ij}^{2}\) corresponding to some \(x_ix_j \in E(G)\) are instead used to ‘force the colorings to be proper’ in G. That is to say that, for a color \(\xi \in \{0,1,2\}\), the times associated with the edge \(e_{ij}^{\xi }\) (Eq. (3)) will prohibit us from entering \(e_i\) at its \(\xi \)-th appearance and also entering \(e_j\) at its \(\xi \)-th appearance (i.e. ‘coloring \(x_i\) and \(x_j\) the same color’).   \(\square \)

Fig. 1.
figure 1

Top left: \(K^3\). Top right: star constructed from \(K^3\). Bottom: times (and corresponding intervals) associated with the edges \(e_1\), \(e_2\) and \(e^0_{1,2}\), \(e^1_{1,2}\), \(e^2_{1,2}\) (time progresses left-to-right and intervals are not drawn to scale). We write \(r_1, r_2, r_3, r_4\) as shorthand for the entries of \(\tau (e^0_{1,2})\) (similarly, for \(i \in [4]\), we write \(g_i\) and \(b_i\) with respect to \(\tau (e^1_{1,2})\) and \(\tau (e^2_{1,2})\)). The red and thick intervals correspond to visits defined by the coloring \(x_i \mapsto i - 1\) of the \(K^3\).

Full size image

Observe that increasing the maximum number of times per edge cannot make the problem easier: we can easily extend the hardness result to any \(k' > 4\) by simply adding a new edge with \(k'\) times all prior to the times that are already in the star. This, together with the fact that Akrida, Mertzios and Spirakis [3] showed that \(\textsc {StarExp}(k)\) is in \(\textsc {NP}\) for all k, allows us to conclude the following corollary.

Corollary 1

For all k at least 4, \(\textsc {StarExp}(k)\) is \(\textsc {NP}\)-complete.

Next we shall reduce \(\textsc {StarExp}(k)\) to \(\textsc {TempEuler}(k-1)\). We point out that, for our purposes within this section, only the first point of the statement of the following result is needed. However, later (in the proof of Corollary 3) we shall make use of the properties stated in the second point of Lemma 1 (this is also why we allow any k times per edge rather than just considering the case \(k = 4\)). Thus we include full details here.

Lemma 1

For all \(k \ge 2\) there is a polynomial-time-computable mapping taking every \(\textsc {StarExp}(k)\) instance \((S_n, \tau )\) to a \(\textsc {TempEuler}(k-1)\) instance \((D_n, \sigma )\) such that

  1. 1.

    \((S_n, \tau )\) is a yes instance for \(\textsc {StarExp}(k)\) if and only if \((D_n, \sigma )\) is a yes instance for \(\textsc {TempEuler}(k-1)\) and

  2. 2.

    \(D_n\) is a graph obtained by identifying n-copies \(\{K^3_1, \ldots , K^3_n\}\) of a cycle on three vertices along one center vertex (see Fig. 2) and such that

    $$\begin{aligned} \max _{t \in \mathbb {N}} |\{&e \in E(D_n): \min (\sigma (e)) \le t \le \max (\sigma (e))\}| \\&\le 3 \max _{t \in \mathbb {N}} |\{e \in E(S_n): \min (\tau (e)) \le t \le \max (\tau (e))\}|. \end{aligned}$$
Fig. 2.
figure 2

The graph \(D_3\) built from \(S_3\) in Lemma 1

Full size image

Since \(\textsc {TempEuler}(k)\) is clearly in \(\textsc {NP}\) (where the circuit acts as a certificate), our desired \(\textsc {NP}\)-completeness result follows immediately from Lemma 1 and Corollary 1.

Corollary 2

\(\textsc {TempEuler}(k)\) is \(\textsc {NP}\)-complete for all k at least 3.

As we noted earlier, \(\textsc {TempEuler}(1)\) is trivially solvable in time linear in the number of edges of the underlying static graph. Thus, towards obtaining a complexity dichotomy for \(\textsc {TempEuler}(k)\), the only case remaining open is when \(k=2\).

Observe that the reduction in Lemma 1 rules out \(\textsc {FPT}\) algorithms with respect to many standard parameters describing the structure of the underlying graph (for instance the path-width is 2 and feedback vertex number is 1). In fact we can strengthen these intractability results even further by showing that \(\textsc {TempEuler}(k)\) is hard even for instances whose underlying static graph has vertex-cover number 2. This motivates our search in Sect. 4 for parameters that describe the structure of the times assigned to edges rather than just the underlying static structure.

Notice that this time we will reduce from \(\textsc {StarExp}(k)\) to \(\textsc {TempEuler}(k)\) (rather than from \(\textsc {StarExp}(k+1)\) as in Lemma 1), so, in contrast to our previous reduction (Lemma 1), the proof of the following result cannot be used to show hardness of \(\textsc {TempEuler}(3)\).

Theorem 2

For all \(k \ge 4\), the \(\textsc {TempEuler}(k)\) problem is \(\textsc {NP}\)-complete even on temporal graphs whose underlying static graph has vertex-cover number 2.

4 Interval-Membership-Width

As we saw in the previous section, both \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k+1)\) are \(\textsc {NP}\)-complete for all \(k \ge 3\) even on instances whose underlying static graphs are very sparse (for instance even on graphs with vertex cover number 2). Clearly this means that any useful parameterization must take into account the temporal structure of the input. Other authors have already proposed measures of this kind such as the temporal feedback vertex number [7] or temporal analogues of tree-width [12]. However these measures are all bounded on temporal graphs for which the underlying static graph has bounded feedback vertex number and tree-width respectively. Our reductions therefore show that \(\textsc {TempEuler}(k)\) is para-\(\textsc {NP}\)-complete with respect to these parameters. Thus we do indeed need some new measure of temporal structure. To that end, here we introduce such a parameter called interval-membership-width which depends only on temporal structure and not on the structure of the underlying static graph. Parameterizing by this measure, we will show that both \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) lie in \(\textsc {FPT}\).

To first convey the intuition behind our width measure, consider again the \(\textsc {TempEuler}(1)\) problem. As we noted earlier, this is trivially solvable in time linear in |E(G)|. The same is true for any \(\textsc {TempEuler}(k)\)-instance \((G, \tau )\) in which every edge is assigned a ‘private’ interval of times: that is to say that, for all distinct edges e and f in G, either \(\max \tau (f) < \min \tau (e)\) or \(\max \tau (e) < \min \tau (f)\). This holds because, on instances of this kind, there is only one possible relative ordering of edges available for an edge-exploration. It is thus natural to expect that, for graphs whose edges have intervals that are ‘almost private’ (defined formally below), we should be able to deduce similar tractability results.

Towards a formalization of this intuition, suppose that we are given a temporal graph \((G, \tau )\) which has precisely two edges e and f such that there is a time t with \(\min \tau (e) \le t \le \max \tau (e)\) and \(\min \tau (f) \le t \le \max \tau (f)\). It is easy to see that the \(\textsc {TempEuler}(k)\) problem is still tractable on graphs such as \((G, \tau )\) since there are only two possible relative edge-orderings for an edge exploration of \((G, \tau )\) (depending on whether we choose to explore e before f or f before e). These observations lead to the following definition of interval-membership-width of a temporal graph (see Fig. 3).

Fig. 3.
figure 3

A temporal star \((S_4, \tau )\) with interval-membership-sequence: \(F_1 = F_2 = \{cw\}\), \(F_3 = \{cw, cx\}\), \(F_4 = F_5 = \{cw, cx, cy\}\), \(F_6 = \{cw, cy\}\) and \(F_7= F_8 = F_9 = \{cw, cz\}\).

Full size image

Definition 2

The interval membership sequence of a temporal graph \((G, \tau )\) is the sequence \((F_t)_{t \in [\varLambda ]}\) of edge-subsets of G where \(F_t:= \{e \in E(G): \min \tau (e) \le t \le \max \tau (e)\}\) and \(\varLambda \) is the lifetime of \((G, \tau )\). The interval-membership-width of \((G, \tau )\) is the integer \(\mathbf{imw} (G, \tau ) := \max _{t \in \mathbb {N}} |F_t|\).

Note that a temporal graph has unit interval-membership-width if and only if every edge is active at times spanning a ‘private interval’. Furthermore, we point out that the interval membership sequence of a temporal graph is not the same as the sequence \((E_t(G, \tau ))_{t \in \mathbb {N}}\). In fact, although \(\max _{t \in \mathbb {N}}|E_t(G, \tau )| \le \mathbf{imw} (G, \tau )\), there exist classes \(\mathcal {C}\) of temporal graphs with unbounded interval-membership-width but such that every temporal graph in \(\mathcal {C}\) satisfies the property that at most one edge is active at any given time. To see this consider any graph H with edges \(e_1, \ldots , e_m\) and let \((H, \nu )\) be the temporal graph defined by \(\nu (e_i) := \{i,m+i\}\). Clearly \(\max _{i \in \mathbb {N}} |E_i(H, \nu )| = 1\), but we have \(\mathbf{imw} (H, \nu ) = m\).

Note that the interval membership sequence of a temporal graph \((G, \tau )\) can be computed in time \(\mathcal {O}(\mathbf{imw} (G, \tau )\varLambda )\) by iterating over the edges of G.

Armed with the notion of interval-membership-width, we will now show that both \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) are in \(\textsc {FPT}\) when parameterized by this measure. We will do so first for \(\textsc {TempEuler}(k)\) (Theorem 3) and then we will leverage the reduction of Lemma 1 to deduce the fixed-parameter-tractability of \(\textsc {StarExp}(k)\) as well (Corollary 3).

Theorem 3

There is an algorithm that decides whether any temporal graph \((G, \tau )\) with n vertices and lifetime \(\varLambda \) is a yes-instance of \(\textsc {TempEuler}(k)\) in time \(\mathcal {O}(w^3 2^w \varLambda )\) where \(w = \mathbf{imw} (G, \tau )\) is the interval-membership-width of \((G, \tau )\).

Proof (Sketch)

Let \((F_t)_{t \in [\varLambda ]}\) be the interval membership sequence of \((G, \tau )\) and suppose without loss of generality that \(F_1\) is not empty.

We will now describe an algorithm that proceeds by dynamic programming over the sequence \((F_i)_{i \in [\varLambda ]}\) to determine whether \((G, \tau )\) is temporally Eulerian. For each set \(F_i\) we will compute a set \(L_i \subseteq F_i^{\{0,1\}} \times V(G) \times V(G)\) consisting of triples of the form (f, s, x) where s and x are vertices in G and f is a function mapping each edge in \(F_i\) to an element of \(\{0,1\}\). Intuitively each entry (f, s, x) of \(L_i\) corresponds to the existence of a temporal walk starting at s and ending at x at time at most i and such that, for any edge \(e\in F_i\), we will have \(f(e) = 1\) if and only if e was traversed during this walk.

We will now define the entries \(L_i\) recursively starting from the dummy set \(L_0 := \{(\mathbf {0}, x, x) :\exists e \in F_1 \text { incident with } x\}\) where \(\mathbf {0}: e \in F_1 \mapsto 0\) is the function mapping every element in \(F_1\) to 0. Take any (f, s, y) in \(F_i^{\{0,1\}} \times V(G) \times V(G)\). For (f, s, y) to be in \(L_i\) we will require there to be an entry (g, s, x) of \(L_{i-1}\) such that

$$\begin{aligned} g(e) = 1 \text { for all } e \in F_{i-1} \setminus F_i \end{aligned}$$
(4)

and such that the one of the following cases holds: either

  • C1 \(y = x\) and \(f(e) = 1\) if and only if \(e \in F_{i-1} \cap F_i\) and \(g(e) = 1\), or

  • C2 there exists an edge xy in G such that:

  • C2.P1 \(xy \in E_i(G, \tau ) \setminus \{e \in F_i: g(e) = 1\}\) and

  • C2.P2 \(f(e) = 1\) if and only if \(g(e) = 1\) or \(e = xy\).

The Cases C1 and C2 correspond to the the two available choices we have when extending a temporal (s, x)-walk at time i: either we stay put at x (Case C1) or we find some new edge xy active at time i (Case C2) which has never been used before (Property C2.P1) and add it to the walk (Property C2.P2). Equation (4) ensures that we filter out partial solutions that we already know cannot be extended to a Eulerian circuit. To see this, note that, if an edge e will never appear again after time \(i-1\) and we have \(g(e) = 0\), then there is no way of extending the temporal walk represented by the triple (g, s, x) to an Eulerian circuit in \((G, \tau )\) because one edge will always be left out (namely the edge e).    \(\square \)

As a corollary of Theorem 3, we can leverage the reduction of Lemma 1 to deduce that \(\textsc {StarExp}(k)\) is in \(\textsc {FPT}\) parameterized by the interval-membership-width.

Corollary 3

There is an algorithm that decides whether a \(\textsc {StarExp}(k)\) instance \((S_n,\tau )\) is explorable in time \(\mathcal {O}(w^3 2^{3w} \varLambda )\) where \(w = \mathbf{imw} (S_n, \tau )\) and \(\varLambda \) is the lifetime of the input.

Proof

By Lemma 1, we know that there is a polynomial-time reduction that maps any \(\textsc {StarExp}(k)\) instance \((S_n, \tau )\) to a \(\textsc {TempEuler}(k-1)\)-instance \((D_n, \sigma )\) such that

$$\begin{aligned} \max _t |\{&e \in E(D_n): \min (\sigma (e)) \le t \le \max (\sigma (e))\}| \\&\le 3 \max _t |\{e \in E(S_n): \min (\tau (e)) \le t \le \max (\tau (e))\}|. \end{aligned}$$

In particular this implies that \(\mathbf{imw} (D_n, \sigma ) \le 3 w\). Thus we can decide whether \((S_n, \tau )\) is explorable in time \(\mathcal {O}(w^3 2^{3w} \varLambda )\) by applying the algorithm of Theorem 3 to \((D_n, \sigma )\).    \(\square \)

5 Win-Win Approach to Regularly Spaced Times

In this section we will find necessary conditions for edge-explorability of temporal graphs with respect to their interval-membership-width. This will allow us to conclude that either we are given a no-instance or that the interval-membership-width is small (in which case we can employ our algorithmic results from the previous section).

We will apply this bidimensional approach to a variants of \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) in which we are given upper and lower bounds (u and \(\ell \) respectively) on the difference between any two consecutive times at any edge. Specifically we will show that \(\textsc {StarExp}(k)\) is in \(\textsc {FPT}\) parameterized by k, \(\ell \) and u (Theorem 4) and that \(\textsc {TempEuler}(k)\) is in \(\textsc {FPT}\) parameterized by k and u (Theorem 5). In other words, these results allow us to trade in the dependences on the interval-membership-width of Corollary 3 and Theorem 3 for a dependences on k, \(\ell \), u and k, u respectively.

We note that, for \(\textsc {StarExp}\) instances, the closer \(\ell \) and u get, the more restricted the structure becomes to the point that the dependence on \(\ell \) and u in the running time of our algorithm vanishes when \(\ell = u\). In particular this shows that the problem of determining the explorability of \(\textsc {StarExp}(k)\)-instances for which consecutive times at each edge are exactly \(\lambda \) time-steps apart (for some \(\lambda \in \mathbb {N}\)) is in \(\textsc {FPT}\) parameterized solely by k (Corollary 4). This partially resolves an open problem of Akrida, Mertzios and Spirakis [3] which asked to determine the complexity of exploring \(\textsc {StarExp}(k)\)-instances with evenly-spaced times.

Towards these results, we will first provide sufficient conditions for non-explorability of any \(\textsc {StarExp}(k)\) instance (Lemma 2). These conditions will depend only on: (1) knowledge of the maximum and minimum differences between any two successive appearances of any edge, (2) on the interval-membership-width and (3) on k.

Lemma 2

Let \((S_n, \tau )\) be a temporal star with at most k times at any edge and such that every two consecutive times at any edge differ at least by \(\ell \) and at most by u. If \((S_n, \tau )\) is explorable, then \(\mathbf{imw} (S_n, \tau ) \le 2(ku + 1)/(\ell + 1)\).

Proof

Let \(\varLambda \) be the lifetime of \((S_n, \tau )\), let \((F_t)_{t \in [\varLambda ]}\) be the interval membership sequence of \((S_n, \tau )\) and choose any \(n \in [\varLambda ]\) such that \(|F_n| = \mathbf{imw} (S_n, \tau )\). Let m and M be respectively the earliest and latest times at which there are edges in \(F_n\) which are active and chose representatives \(e_m\) and \(e_M\) in \(F_n\) such that \(m = \min \tau (e_m)\) and \(M = \max \tau (e_M)\).

Recall that visiting any edge e in \(S_n\) requires us to us pick two appearances (which differ by at least \(\ell +1\) time-steps) of e (one appearance to go along e from the center of \(S_n\) to the leaf and another appearance to return to the center of the star). Thus, whenever we specify how to visit an edge e of \(F_n\), we remove at least \(\ell + 1\) time-steps from the available time-set \(\{m, \ldots , M\}\) at which any other edge in \(F_n\) can be visited. Furthermore, since any exploration of \((S_n, \tau )\) must explore all of the edges in \(F_n\), for \((S_n, \tau )\) to be explorable, we must have \(|F_n|(\ell +1) \le M - m + 1\). This concludes the proof since \(\mathbf{imw} (S_n, \tau ) = |F_n|\) and \(M - m \le |\max \tau (e_M) - \min \tau (e_M)| + |\max \tau (e_m) - \min \tau (e_m)|\) (since, by the definition of \(F_n\), n is in the intervals of any two elements of \(F_n\)) which is at most \(2ku +1\) (since consecutive times at any edge differ by at most u).   \(\square \)

Notice that nearly-identical arguments yield the following slightly weaker result with respect to the \(\textsc {TempEuler}(k)\) problem.

Lemma 3

Let \((G, \tau )\) be a \(\textsc {TempEuler}(k)\) instance such that every two consecutive times at any edge differ at most by u. If \((G, \tau )\) is temporally Eulerian, then \(\mathbf{imw} (G, \tau ) \le 2(ku + 1)\).

The reason that the we can only bound \(\mathbf{imw} (G, \tau )\) above by \(2(ku + 1)\) (rather than \(2(ku + 1)/(\ell + 1)\) as in the \(\textsc {StarExp}(k)\) case of Lemma 2) is that temporal Euler circuits only visit each edge once (so exploring each edge only removes exactly one available time).

Lemma 2 allows us to employ a ‘win-win’ approach for \(\textsc {StarExp}(k)\) when we know the maximum difference between consecutive times at any edge: either the considered instance does not satisfy the conditions of Lemma 2 (in which case we have a no-instance) or the interval-membership-width is ‘small’ (in which case we apply the algorithm given by Corollary 3). These ideas allow us to conclude the following result.

Theorem 4

Let \((S_n, \tau )\) be a temporal star with at most k times at any edge and such that every two consecutive times at any edge differ at least by \(\ell \) and at most by u. There is an algorithm deciding whether \((S_n, \tau )\) is explorable in time \(2^{\mathcal {O}(ku/\ell )} \varLambda \) where \(\varLambda \) is the lifetime of the input.

Proof

The algorithm proceeds as follows. First determine \(\mathbf{imw} (S_n, \tau )\) (this can be done in time \(\mathcal {O}(\varLambda n)\) where \(\varLambda \) is the lifetime of the input). If \(\mathbf{imw} (S_n, \tau ) > 2(ku + 1)/(\ell + 1)\), then \((S_n, \tau )\) is not explorable by Lemma 2. Otherwise run the algorithm given in Corollary 3. In this case, since \(w := \mathbf{imw} (S_n, \tau ) \le 2(ku + 1)/(\ell + 1)\), we know that the algorithm of Corollary 3 will run on \((S_n,\tau )\) in time \(2^{\mathcal {O}(ku/\ell )} \varLambda \).    \(\square \)

Once again arguing by bidimensionality (this time using Lemma 3 and Theorem 3) we can deduce the following fixed-parameter tractability result for \(\textsc {TempEuler}\).

Theorem 5

Let \((G, \tau )\) be a \(\textsc {TempEuler}(k)\) instance such that every two consecutive times at any edge differ at most by u. There is an algorithm deciding whether \((G, \tau )\) is temporally Eulerian in time \(2^{\mathcal {O}(ku)} \varLambda \) where \(\varLambda \) is the lifetime of the input.

As a special case of Theorem 4 (i.e. the case where \(\ell = u\)) we resolve an open problem of Akrida, Mertzios and Spirakis [3] which asked to determine the complexity of exploring \(\textsc {StarExp}(k)\)-instances with evenly-spaced times. In particular we show that the problem of deciding the explorability of such evenly-spaced \(\textsc {StarExp}(k)\)-instances is in \(\textsc {FPT}\) when parameterized by k.

Corollary 4

There is an algorithm which, given any \(\textsc {StarExp}(k)\) instance \((S_n, \tau )\) with lifetime \(\varLambda \) and in which every two pairs of consecutive times assigned to any edge differ by the same amount, decides whether \((S_n, \tau )\) is explorable in time \(2^{\mathcal {O}(k)} \varLambda \).

6 Discussion

We introduced a natural temporal analogue of Eulerian circuits and proved that, in contrast to the static case, \(\textsc {TempEuler}(k)\) is \(\textsc {NP}\)-complete for all \(k\ge 3\). In fact we showed that the problem remains hard even when the underlying static graph has path-width 2, feedback vertex number 1 or vertex cover number 2. Along the way, we resolved an open problem of Akrida, Mertzios and Spirakis [3] by showing that \(\textsc {StarExp}(k)\) is \(\textsc {NP}\)-complete for all \(k \ge 4\). This result yields a complete complexity dichotomy with respect to k when combined with Akrida, Mertzios and Spirakis’ results [3]; however, a similar dichotomy for \(\textsc {TempEuler}(k)\) still eludes us. In fact, although we know that \(\textsc {TempEuler}(1)\) is in \(\textsc {P}\), our reduction cannot be extended to obtain a complete dichotomy result. Thus to determine the complexity of the only remaining open case (i.e. \(\textsc {TempEuler}(2)\)) new ideas are needed.

Our hardness results rule out the possibility of obtaining \(\textsc {FPT}\) algorithms for \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) with respect to many standard parameters describing the structure of the underlying graph (such as path-width, feedback vertex number and vertex-cover number). We thus introduced a new width measure which captures structural information that is purely temporal; we call this the interval-membership-width. In contrast to our hardness results, we showed that \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) can be solved in times \(\mathcal {O}(w^3 2^w \varLambda )\) and \(\mathcal {O}(w^3 2^{3w} \varLambda )\) respectively where w is our new parameter and \(\varLambda \) is the lifetime of the input.

Our fixed-parameter-tractability results parameterized by interval-membership-width can also be leveraged via a win-win approach to obtain tractability results for both \(\textsc {TempEuler}(k)\) and \(\textsc {StarExp}(k)\) parameterized solely by k and the spacing of appearances of edges in the input. These results allow us to partially resolve another open problem of Akrida, Mertzios and Spirakis concerning the complexity of \(\textsc {StarExp}(k)\): we showed that it can be solved in time \(2^{\mathcal {O}(k)}\varLambda \) when the input has evenly spaces appearances of each edge and lifetime \(\varLambda \). We note, however, that it remains an open problem to determine the complexity of the evenly-spaced \(\textsc {StarExp}(k)\) problem when k is unbounded.

Finally we point out that all of our hardness reductions hold also for the case of non-strict temporal walks and, with slightly more work, this also holds for our tractability results.