Timeline Problems in Temporal Graphs:
Vertex Cover vs. Dominating Set

Rozenshtein et al. [28] showed that Timeline VC is NP-hard in general, but solvable in polynomial time for $k=1$. Froese et al. [18] continued the algorithmic study of Timeline VC. They proved NP-hardness even if the input consists of at most three snapshots, $k=2$ and $\mathrm{\ell }=0$ and studied the parameterized complexity with respect to different parameters. Froese et al. [18] showed fixed-parameter tractability for $n+k$ and $\mathrm{W}$[1]-hardness for $n+\mathrm{\ell }$. Herein, $n$ is the number of vertices of the underlying graph which in turn is the static graph obtained by taking the union of all edge sets. Moreover, Timeline VC admits an XP-algorithm for $n$ and is fixed-parameter tractable with respect to $n$ if $\mathrm{\ell }=0$ [18]. Schubert [29] later analyzed the parameterized complexity of Timeline VC with respect to combinations of input parameters with structural parameters of the underlying graph. Finally, Dondi et al. [12] obtained two results for Timeline PVC with $k=1$: First, it was shown that this case is NP-hard, in contrast to Timeline VC. Second, Dondi et al. [12] gave FPT-algorithms for parameterization by the number of covered edges and by the number of uncovered edges.

We start off with a new hardness result for Timeline VC: We show that the problem remains NP-hard even if the total number of snapshots $T$, $k$, and $\mathrm{\ell }$ are constant and additionally the maximum degree in every snapshot is at most one. Then, we show the NP-hardness of Timeline DS, again for the case that $T$, $k$, and $\mathrm{\ell }$ are constant and the maximum snapshot degree is one.

We then study the parameterized complexity of the problems; an overview of the results is given in Table 1. As noted above, Timeline VC is fixed-parameter tractable with respect to $n+k$ [18]. Since $n$ is a rather large parameter, Froese et al. [18] asked whether there are FPT-algorithms also for parameters that are smaller than $n$. We make progress in this direction by considering the two parameters interval-membership-width $(\mathrm{imw})$ and vertex-interval-membership-width $(\mathrm{vimw})$ which where introduced by Bumpus and Meeks [3]. The parameters $\mathrm{imw}$ and $\mathrm{vimw}$ are interesting in the sense that they are among the relatively few truly temporal structural graph parameters because they are sensitive to the order of the snapshots [3]. Informally, $\mathrm{vimw}$ can be defined as follows: We say the lifetime of a vertex is the time interval between its first and last non-isolated appearance in a snapshot. For a timestep $i$, the bag of $i$ is the set of vertices whose lifetime contains timestep $i$, and $\mathrm{vimw}$ is the size of the largest bag of $𝒢$.

We first show that Timeline PVC is fixed-parameter tractable with respect to $\mathrm{vimw}+k+\mathrm{\ell }$. To further improve on this, we introduce a hierarchy of parameters with non-increasing size. The idea, inspired by the $h$-index of static graphs [16], is that a temporal graph may have only few large bags. In that case, we would rather parameterize by the size of the $x$th largest bag, denoted by $\mathrm{vimw}[x]$, for some $x>1$. With this definition, we have $\mathrm{vimw}=\mathrm{vimw}[1]$ and $\mathrm{vimw}[x]\ge \mathrm{vimw}[x+1]$ for all $x\in [T]$. We show that Timeline PVC is fixed-parameter tractable for $\mathrm{vimw}[x]+k+\mathrm{\ell }$ with $x=k\cdot (\mathrm{\ell }+1)$. Informally, this means that the larger $k$ and $\mathrm{\ell }$ get, the more large bags can be ignored for the parameter. We then consider Timeline (Partial) Dominating Set in the same setting. We first showing fixed-parameter tractability of Timeline PDS for $\mathrm{vimw}+k+\mathrm{\ell }$. Then we show that for Timeline DS it can be improved to fixed-parameter tractability for $\mathrm{vimw}[x]+k+\mathrm{\ell }$ for $x=\mathrm{\ell }+2$ while for Timeline PDS parameterization by $\mathrm{vimw}[2]+k+\mathrm{\ell }$ is not useful. The latter result is obtained by showing NP-hardness of the extremely restricted special case when there are two snapshots, one of which is edgeless, $k=1$ and $\mathrm{\ell }=0$.

Afterwards, we consider the interval-membership-width $(\mathrm{imw})$. Informally, this is the edge-version of $\mathrm{vimw}$, that is, the bag at timestep $i$ contains the edges which occur at timestep $i$ and those that occur both before and after $i$. Note that $\mathrm{imw}$ can be considered to be a smaller parameter than $\mathrm{vimw}$: For all instances, we have $\mathrm{vimw}\in \mathrm{\Omega }(\sqrt{\mathrm{imw}})$ and there are instances with constant values of $\mathrm{imw}$ and unbounded values of $\mathrm{vimw}$. We show that Timeline DS is fixed-parameter tractable for the parameter $\mathrm{imw}+k+\mathrm{\ell }$ while all three other problems are NP-hard for constant values of $\mathrm{imw}+k+\mathrm{\ell }$. Given the latter hardness results, we refrain from analyzing a hierarchy of $\mathrm{imw}$-based parameters. Altogether, the results show that in our setting, $\mathrm{vimw}$ is a much more powerful parameter than $\mathrm{imw}$.

We then conclude by considering the more standard parameters $n$, $k$, $\mathrm{\ell }$, and $t$, where $t$ denotes the number of vertices to dominate or edges to cover, respectively. For Timeline DS, we show fixed-parameter tractability for $n+k$ and $\mathrm{W}$[1]-hardness for $n+\mathrm{\ell }$, thus showing that the complexity is similar to the one of Timeline VC. Finally, we show that Timeline PDS and Timeline PVC can be solved in $2^{𝒪(t)}\cdot {(n+T)}^{𝒪(1)}$ time. This improves and extends a previous result of Dondi et al. [12, Thm. 6] who provided an algorithm for Timeline PVC with $k=1$ that has running time $2^{t\cdot \log (t)}\cdot {(n+T)}^{𝒪(1)}=t^t\cdot {(n+T)}^{𝒪(1)}$.

Proofs of statements marked with $(\star )$ are deferred to the related full version.

Akrida et al. [1] introduced the problems Temporal Vertex Cover (TVC) and Sliding Window Temporal Vertex Cover (SW-TVC), where the goal is to find a minimum number of temporal vertices that cover the edges of the temporal graph. In TVC each edge needs to be covered in at least one of the snapshots and in SW-TVC, the input contains an integer $\mathrm{\Delta }$, and the aim is to cover every edge at least once at every $\mathrm{\Delta }$ consecutive time steps. Akrida et al. [1] showed that TVC remains NP-hard when the underlying graph is a star graph. Moreover, they studied the approximability of both problems, provided (S)ETH-based running time lower bounds and designed an exact dynamic programming algorithm with exponential running time. The research on these problems was then continued by Hamm et al. [20], who showed that TVC is solvable in polynomial time if the underlying graph is a path or cycle while SW-TVC remains NP-hard in this case. Besides that, they provided several (exact and approximation) algorithms for the sliding window variant. The Temporal Dominating Set (TDS) problem is defined analogously, here the task is to dominate every vertex in at least one of the snapshots of the temporal graph by selecting few temporal vertices. TDS is NP-hard in very restricted cases, for example when the maximum degree in every snapshot is 2 [22]. There are further temporal variants of Vertex Cover and Dominating Set which have been discussed and studied. These include a multistage variant of Vertex Cover [17], a reachability-based variant for Dominating Set [23] and different conditions on how and when a vertex should be dominated [4, 31].

A (static) graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$. We denote by $V(G)$ and $E(G)$ the vertex and edge set of $G$, respectively. Furthermore, we let $n:=|V(G)|$ and $m:=|E(G)|$. For an edge $\{u,v\}$ we write $uv$ and call $u$ and $v$ endpoints of the edge. Further, we say that the vertex $v\in V$ is incident with $e\in E$ if $v\in e$. If $uv\in E$, then $u$ and $v$ are adjacent and they are neighbors of each other. The set $N_G(v):=\{u\in V:u\text{ and }v\text{ are adjacent}\}$ is the (open) neighborhood of $v$. Moreover, $N_G[v]:=N_G(v)\cup \{v\}$ is the closed neighborhood of $v$. For a set of vertices $S$, we let $N_G[S]:={\bigcup }_{s\in S}{N}_G[s]$ and $N_G(S)=N_G[S]\setminus S$. By ${\mathrm{deg}}_G(v):=|N_G(v)|$ we denote the degree of $v$. If ${\mathrm{deg}}_G(v)=0$, we say that $v$ is isolated. The maximum degree is $\mathrm{\Delta }(G):={\max }_{v\in V}{\mathrm{deg}}_G(v)$. For vertex sets $S$ and $T$, we let $E_G(S,T):=\{uv\in E(G):u\in S\text{ and }v\in T\}$ and we let $E(S):=E(S,S)$. A graph $G$ is bipartite if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $E(G)=E(S,T)$. For more details on graph theory, we refer to the book by Diestel [8].

A temporal graph $𝒢$ is a finite sequence of graphs $(G_1,\mathrm{\dots },G_T)$ which all have the same set of vertices $V(𝒢):=V(G_1)=\mathrm{\cdots }=V(G_T)$. The graphs $G_i$ are called snapshots, $T$ is the lifetime of $𝒢$, and $i\in [T]$ is a time step. We may write $V$ instead of $V(𝒢)$ and $E_i$ instead of $E(G_i)$. Moreover, for $u,v\in V$ and $i\in [T]$, $(v,i)$ is a temporal vertex and $(\{u,v\},i)=(uv,i)$ with $uv\in E_i$ is a temporal edge in snapshot $G_i$. We say edge $e$ appears in $G_i$ if $e\in E_i$. Moreover, we say that a vertex $v$ is incident with the temporal edge $(e,i)$ if $v\in e$. For a temporal vertex $(v,i)$, we define the (open) neighborhood by $N_{𝒢}((v,i)):=N_{G_i}(v)$ and the closed neighborhood by $N_{𝒢}[(v,i)]:=N_{G_i}[v]$. By $G_{\downarrow }(𝒢):=(V_{\downarrow }:=V(𝒢),E_{\downarrow }:={\bigcup }_{i=1}^T{E}_i)$ we denote the underlying graph of $𝒢$. We let ${\mathrm{\Delta }}_i(𝒢)=\mathrm{\Delta }(G_i)$. Furthermore, by ${\mathrm{\Delta }}_{\max }(𝒢):={\max }_{i=1}^T{\mathrm{\Delta }}_i(𝒢)$ we denote the maximum snapshot degree of $𝒢$. If $E_i=\mathrm{\varnothing }$ we say that $G_i$ is empty. We may drop the subscript ${\cdot }_{𝒢}$ when it is clear from context.

We give the precise definitions of the parameters related to the (vertex)-interval-membership width: $\mathrm{vimw}$, $\mathrm{vimw}[x]$, and $\mathrm{imw}$.

Let $𝒢=(G_1,\mathrm{\dots },G_T)$ be a temporal graph. The vertex-interval-membership sequence of $𝒢$ is the sequence ${(F_i)}_{i\in [T]}$ of vertex-subsets $F_i\subseteq V(𝒢)$ (called bags), where each $F_i$ is defined as

The vertex-interval-membership-width of $𝒢$, denoted by $\mathrm{vimw}(𝒢)$, is the maximum size of a bag in the vertex-interval-membership sequence, that is, $\mathrm{vimw}(𝒢):=\max \{|F_i|:i\in [T]\}$.

For given $x\in [T]$ we introduce the parameter $\mathrm{vimw}[x]$ as the size of the $x$th largest bag of the vertex-interval-membership sequence. Formally, let $(F_{i_1},\mathrm{\dots },F_{i_T})$ be an ordering of ${(F_i)}_{i\in [T]}$ such that $|F_{i_1}|\ge \mathrm{\cdots }\ge |F_{i_T}|$. Then we define

Note that $\mathrm{vimw}[i]$ can be much smaller than $\mathrm{vimw}[1]=\mathrm{vimw}$: for example consider a temporal graph where every vertex only appears non-isolated for a short period of time. If all snapshots have only a few edges, then $\mathrm{vimw}$ is small. However, a single snapshot with many edges is enough to make $\mathrm{vimw}$ arbitrarily large. If only a few such snapshots exist, then $\mathrm{vimw}[i]$ is already much smaller then $\mathrm{vimw}$ for small $i$.

The interval-membership sequence of $𝒢$ is the sequence ${(F_i)}_{i\in [T]}$ of edge-subsets $F_i\subseteq E_{\downarrow }$ (again called bags), where each $F_i$ is defined as

The interval-membership-width of $𝒢$, denoted by $\mathrm{imw}(𝒢)$, is the maximum size of a bag in the interval-membership sequence, that is, $\mathrm{imw}(𝒢):=\max \{|F_i|:i\in [T]\}$.

We remark that $\mathrm{vimw}=\mathrm{\Omega }(\sqrt{\mathrm{imw}})$ and that there exist temporal graphs with $\mathrm{imw}=1$ but arbitrary large $\mathrm{vimw}$ [3]. Finally, note that the vertex-interval-membership sequence and the interval-membership sequence can be computed in polynomial time with respect to the input size.

Given a temporal graph $𝒢=(G_1,\mathrm{\dots },G_T)$, an activity interval of a vertex $v$ is a triple $(v,a,b)\in V(𝒢)\times [T]\times [T]$ such that $a\le b$. We say $a$ that is the starting time and $b$ is the end time of an activity interval $(v,a,b)$. The length of the activity interval is defined by $b-a$. A $k$-activity timeline of the temporal graph $𝒢$ is a set of activity intervals $𝒯\subseteq \{(v,a,b)\in V(𝒢)\times [T]\times [T]:a\le b\}$, which contains at most $k$ activity intervals for each vertex. A $k$-activity $\mathrm{\ell }$-timeline is a $k$-activity timeline in which each activity interval has length at most $\mathrm{\ell }$. Given a $k$-activity timeline $𝒯$, a vertex $v$ is called active in snapshot $G_i$, if there exists $(v,a,b)\in 𝒯$ such that $a\le i\le b$. A $k$-activity timeline $𝒯$ dominates the temporal vertex $(v,i)$ if $v\in N_{G_i}[\{u:u\text{ is active in }{G}_i\}]$. A $k$-activity timeline $𝒯$ covers the temporal edge $(e,i)$ if at least one of the two endpoints of $e$ is active in snapshot $G_i$.

Let $L\subseteq {\mathrm{\Sigma }}^{\ast }$ be a computational problem specified over some alphabet $\mathrm{\Sigma }$ and let $p:{\mathrm{\Sigma }}^{\ast }\to \mathbb{N}$ be a parameter, that is, $p$ assigns to each instance of $L$ an integer parameter value (which we simply denote by $p$ if the instance is clear from the context). We say that $L$ is fixed-parameter tractable (FPT) with respect to $p$ if $L$ can be decided in $f(p)\cdot {|I|}^{𝒪(1)}$ time where $|I|$ is the length of the input. The corresponding hardness concept related to fixed-parameter tractability is W[$t$]-hardness, $t\ge 1$; if a problem $L$ is W[$t$]-hard with respect to $p$, then $L$ is assumed to not be fixed-parameter tractable. Moreover, $L$ is slice-wise polynomial (XP) with respect to $p$ if $L$ can be decided in $f(p)\cdot {|I|}^{g(p)}$ time. Let $(I,p)$ and $(I^{\prime },p^{\prime })$ be two instances of $L$. A reduction to a (problem) kernel for $L$ is a polynomial-time algorithm that computes an instance $(I^{\prime },p^{\prime })$ such that

• $\mathrm{■}$

  $p^{\prime }+|I^{\prime }|\le g(p)$, and

• $\mathrm{■}$

  $(I,p)$ is a yes-instance of $L$ if and only if $(I^{\prime },p^{\prime })$ is a yes-instance of $L$.

The instance $(I^{\prime },p^{\prime })$ is referred to as the problem kernel and $g$ is the size of the kernel. Furthermore, if $g$ is a polynomial, we say that the kernel is a polynomial problem kernel. For more details about parameterized complexity we refer to the standard monographs [14, 7].

We reduce from the NP-hard problem $3$-Coloring on graphs with maximum degree four [19]. In $3$-Coloring the input is a graph and the question is whether the vertices can be colored with three colors such that no two adjacent vertices have the same color.

The basic idea is to construct a temporal graph with three parts $C_1,C_2$ and $C_3$ (call them color blocks), each consisting of five snapshots and representing one of the three colors. The part in which a vertex $v$ is not active corresponds to the assigned color of $v$. As each of the three parts will contain every edge of $G$ and only vertices of degree at most one, this ensures that all neighbors are active in the part where $v$ is not active. Hence, they are assigned a different color. The basic idea for encoding a given graph $G$ into snapshots of maximum degree one is to find a proper edge coloring with five colors and split the edge set with respect to this coloring, which can be done in polynomial time via Vizing’s theorem. Our aim is that no activity interval of any vertex can hit more than one color block. To ensure this, we add sufficiently many empty snapshots between any two parts.

Let $(G=(V=\{v_1,\mathrm{\dots },v_n\},E))$ be an instance of $3$-Coloring on graphs with maximum degree four. We construct the following temporal graph $𝒢$ where $V(𝒢)=V$.

The temporal graph $𝒢$ consists of $23$ snapshots. It can be seen as a sequence of five parts, namely $C_1,H_1,C_2,H_2,C_3$. Parts $H_1$ and $H_2$ consist of $4$ empty snapshots and each of $C_1,C_2,C_3$ consists of 5 snapshots. Thus, snapshots $6$ to $9$ and $15$ to 18 are empty. We denote $H_1$ and $H_2$ as the empty blocks and we call $C_1,C_2$ and $C_3$ color blocks as they correspond to the three colors. In the following we formally define the snapshots of the color blocks. All three color blocks $C_1,C_2$ and $C_3$ will be identical. Hence, we only formally define $C_1$, that is, snapshots 1 to 5.

Here we exploit the fact that the graph $G$ has maximum degree four, because this implies that there exists a proper edge coloring with at most five colors due to Vizing’s theorem [32], which can be computed in polynomial time [25]. Let $E(G)=F_1\cup \mathrm{\cdots }\cup F_5$ be the partition of $E(G)$ into five colors of some proper edge coloring. Now, snapshot $j$ contains exactly the edges of $F_j$. Finally, observe that by construction, the maximum degree in each snapshot is at most one. By setting $k=2$ and $\mathrm{\ell }=4$, we obtain the Timeline VC instance $(𝒢,k,\mathrm{\ell })$.

We show that $G$ is $3$-colorable if and only if $𝒢$ has a $2$-activity $4$-timeline $𝒯$ covering all temporal edges of $𝒢$. In the following we say a vertex $v$ is active during $C_j$ for $j\in [3]$ to indicate that an activity interval of $v$ starts at the first time step and ends and the last time step of the corresponding part.

$(\Rightarrow )$ Let $\varphi :V(G)\to [3]$ be a proper 3-coloring of $G$. We construct an activity timeline of $𝒢$ which covers all temporal edges. For each $i\in [n]$, the vertex $v\in V(G)$ is active in the two color blocks, which do not correspond to the assigned color of $v$. Clearly, this yields a 2-activity timeline $𝒯$. It remains to argue that each temporal edge is covered by $𝒯$. Since $\varphi$ is a proper 3-coloring, both endpoints of each edge $uw\in E(G)$ have a different color. Moreover, since in color block $C_j$ all vertices are active which do not have color $j$, we conclude that all temporal edges of $𝒢$ are covered by $𝒯$.

$(\Leftarrow )$ Let $𝒯$ be a $2$-activity 4-timeline covering all temporal edges of $𝒢$. Observe that since parts $H_1$ and $H_2$ corresponding to snapshots 6 to 9 and 15 to 18 are empty, no activity interval of any vertex can hit more than one color block. Consequently, since $k=2$, for each vertex $v$ there exists at least one color $j\in [3]$ such that $v$ is not active during any snapshot of color block $C_j$. Let $\varphi (v)\in [3]$ be such a color. Note that if $\varphi (v)$ is not unique, we pick any color fulfilling the property. We now argue that $\varphi$ is a proper 3-coloring of $G$. Assume towards a contradiction that this is not the case, that is, there exists at least one edge $uw\in E(G)$ such that both endpoints $u$ and $w$ have the same color $j$. This implies that both $u$ and $w$ are not active during $C_j$. But since exactly one of the 5 snapshots corresponding to color block $C_j$ contains the edge $uw$, timeline $𝒯$ is not covering all temporal edges of $𝒢$, a contradiction. Thus, $\varphi$ is a proper 3-coloring of $G$. $◀$ Next, we extend the ideas of this reduction to Timeline DS for which the reduction is more involved since we also need to deal with isolated temporal vertices.