Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions

We present a polynomial-time reduction from Hitting Set, which is NP-hard and $\mathrm{W}[2]$-hard when parameterized by the size $k$ of the sought solution.

Let $I:=(U,F,k)$ be an instance of Hitting Set and assume without loss of generality that each hyperedge of $F$ is non-empty, as otherwise, $I$ is a trivial no-instance. Fix some arbitrary order on $U$ and consider the following temporal graph $𝒢$. The vertex set consists of one vertex $v_e$ for each hyperedge $e\in F$, and one center vertex $c$. Further, we introduce for each element $u_i\in U$ one snapshot $G_i$ in which the center is connected to exactly those vertices $v_e$ for which the hyperedge $e$ contains $u_i$. By construction, $G_{\downarrow }$ is a star graph. Clearly, this reduction can be done in polynomial time.

Correctness: We show that $F$ has a hitting set of size at most $k$ if and only if $𝒢$ has a temporal dominating set $𝒮$ of size at most $k$.

($\Rightarrow$) Let $S\subseteq U$ be a hitting set of size at most $k$ for $F$. For each $u_i\in S$, we add the temporal vertex $(c,i)$ to $𝒮$. For each hyperedge $e\in F$ there exists a $u_i\in S$ such that $u_i\in e$ since $S$ is a hitting set. By construction, the temporal vertex $(c,i)$ dominates the vertex $v_e$ because $c{v}_e\in E_i$. It follows immediately that the chosen temporal vertices are a temporal dominating set of $𝒢$.

($\Leftarrow$) Let $𝒮$ be a temporal dominating set of $𝒢$ of size at most $k$. Note that we can assume that $𝒮$ only contains temporal vertices of the center vertex $c$, that is, $𝒮\subseteq \{(c,i):i\in [1,|U|]\}$. This is due to the fact that, for each temporal vertex $(v_e,i)$ with $v_e\ne c$ there exists a snapshot $G_j$ such that $c{v}_e\in E_j$ and consequently the temporal vertex $(v_e,i)$ dominates a subset of the vertices dominated by $(c,j)$. Consider the set $S$ obtained by adding $u_i$ to $S$ if $(c,i)$ is in the temporal dominating set $𝒮$. For each $e\in F$, the vertex $v_e$ is dominated by some vertex $(c,i)\in 𝒮$. By construction, $u_i\in S$ and $u_i\in e$. Consequently, $S$ is a hitting set of size at most $k$ for $F$. $◀$

If we reduce from the NP-hard special case [18] of Hitting Set where each hyperedge has size $2$ and each element occurs in at most three hyperedges, the resulting temporal graph has at most three edges in each snapshot, and each edge appears in at most two snapshots, which implies the following.

Due to the NP-hardness for underlying stars, parameterized algorithms for a large number of parameters of the underlying graph are impossible. The next results show that even if the underlying graph is a clique, the problem remains NP-hard even for very restricted number of edges in each snapshot. Note that this also bounds the maximum snapshot degree ${\mathrm{\Delta }}_{\max }$.

We provide a reduction from Exact Cover By $3$-Sets (X3C) [18]. The input of the problem consists of a finite set $X=\{x_1,\mathrm{\dots },x_{3q}\}$ together with a family $ℱ=\{F_1,\mathrm{\dots },F_p\}$ of size-3 subsets of $X$ and the question is whether there is a subset $𝒞$ of $ℱ$ such that each $x_j$ appears in exactly one set from $𝒞$ (this implies $|𝒞|=q$).

Consider a temporal graph $𝒢$ with vertex set $V(𝒢):=\{v_j:x_j\in X\}$ and $p+\left(\genfrac{}{}{0pt}{}{3q}{2}\right)$ snapshots. For $i\in [p]$ let $j(i):=\min \{s\in [3q]:x_s\in F_i\}$ and define the edge set $E_i:=\{v_{j(i)}{v}_s:s\ne j(i),x_s\in F_i\}$. The purpose of the remaining $\left(\genfrac{}{}{0pt}{}{3q}{2}\right)$ snapshots is to ensure that the underlying graph is a clique. This can be done by adding for each pair of elements $x_r,x_s\in X$ one snapshot which only contains the edge $v_r{v}_s$. By construction, the underlying graph is a clique and there are at most two edges in each snapshot. Clearly, this reduction can be done in polynomial time.

Correctness: We show that $(X,ℱ)$ is a yes-instance of X3C if and only if $(𝒢,q)$ is a yes-instance of TDS.

($\Rightarrow$) Suppose each element from $X$ appears in exactly one set from $𝒞\subseteq ℱ$. Recall that this implies that $𝒞$ has size $q$. Consider the following temporal vertex set $𝒮$. For each $F_i\in 𝒞$ we add the temporal vertex $(v_{j(i)},i)$ to $𝒮$. Clearly, $(v_{j(i)},i)$ dominates exactly the vertices from $V(𝒢)$ which correspond to the elements from $F_i$. Since every element of $X$ is contained in a set from $𝒞$, it follows that every vertex from $V(𝒢)$ is dominated.

($\Leftarrow$) Suppose that $𝒮$ is a temporal dominating set of size $q$ for $𝒢$. Since each snapshot contains at most two edges and $|V(𝒢)|=3q$, it is clear that each temporal vertex from $𝒮$ dominates exactly three vertices which are not dominated by any other temporal vertex from $𝒮$. By construction, it follows that $𝒮\subseteq \{(v_{j(i)},i):i\in [p]\}$, since only these temporal vertices can dominate more than two vertices in their respective snapshot. We obtain a solution $𝒞$ to the X3C instance by adding $F_i$ to $𝒞$ if and only if $𝒮$ contains a temporal vertex from the $i$th snapshot, that is, the temporal vertex $(v_{j(i)},i)$. Observe that by definition of the first $p$ snapshots, the set $F_i\in 𝒞$ covers exactly the elements from $X$ whose corresponding vertices are dominated by $(v_{j(i)},i)\in 𝒮$. This implies that every element of $X$ is contained in exactly one set from $𝒞$, since $𝒮$ dominates each vertex exactly once. $◀$

We now show a similar hardness result for Temporal Vertex Cover with a slightly larger snapshot degree on instances with a clique as underlying graph. Recall that for instances with a star as underlying graph, TVC is known to be NP-hard [1, Thm. 2].

Let $I=(𝒢,k,t)$ be an instance of TPVC. Without loss of generality we assume that $|E(G_{\downarrow })|\ge t$ and that $2k\ge t$ since otherwise the instance is a trivial no-instance. Moreover, let $𝒮$ be a solution of $I$ and let $F\subseteq E(G_{\downarrow })$ be the set of covered edges by $𝒮$. Since the maximum snapshot degree is two, each vertex in $𝒮$ can cover at most two edges of $G_{\downarrow }$. Consequently, each vertex in $𝒮$ covers either a single edge of $G_{\downarrow }$ or a pair of adjacent edges of $G_{\downarrow }$, that is, a $P_3$.

Now, we consider a mapping $\varphi :F\to 𝒮$ such that each edge in $F$ is mapped to one of its endpoints in $𝒮$. Let ${𝒮}_2\subseteq 𝒮$ be the set of temporal vertices such that exactly two edges of $F$ are mapped to each temporal vertex in ${𝒮}_2$. Next, we show that maximizing the number of covered edges is equivalent to maximizing the number of edge-disjoint $P_3$s. More precisely, we prove that $𝒮$ is a solution if and only if $|{𝒮}_2|\ge t-k$: Each temporal vertex in ${𝒮}^{\ast }:=𝒮\setminus {𝒮}_2$ can cover at most one edge of $E(G_{\downarrow })$ according to $\varphi$. Moreover, let $F^{\ast }:=\{f\in F:\varphi (f)\notin {𝒮}_2\}$. Since each temporal vertex in $S^{\ast }$ covers at most one edge of $E(G_{\downarrow })$ according to $\varphi$, we have $|F^{\ast }|\le |S^{\ast }|$. Hence, we obtain $|𝒮|=k=|{𝒮}_2|+|{𝒮}^{\ast }|$ and $t\le |F|=2|{𝒮}_2|+|F^{\ast }|\le |{𝒮}_2|+|{𝒮}^{\ast }|=k+|{𝒮}_2|$ implying $|{𝒮}_2|\ge t-k$.

Consequently, we need to find a set $T$ of at least $t-k$ temporal vertices such that each temporal vertex of $T$ covers a $P_3$ of $G_{\downarrow }$ such that all these $P_3$s are edge-disjoint. Afterwards, we can greedily add $(2k-t)$ temporal vertices to $T$ which cover exactly one so-far uncovered edge of $G_{\downarrow }$ to obtain a solution for $(𝒢,k,t)$. This is always possible due to our assumptions that $|E(G_{\downarrow })|\ge t$ and that $2k\ge t$.

It remains to maximize the number of these edge-disjoint $P_3$s. However, since some pairs of adjacent edges, that is, some non-induced $P_3$s, of $G_{\downarrow }$ might not appear together in one snapshot, we cannot simply find a maximum packing of edge-disjoint $P_3$s in $G_{\downarrow }$. Thus, essentially we are given the underlying graph $G_{\downarrow }$ and a list of possible $P_3$s, that is, pairs of adjacent edges appearing in a common snapshot, and the task is to find a maximum packing of such $P_3$s. This problem is known as Edge Disjoint List $P_3$-Packing and can be solved in polynomial time via a reduction to Maximum Matching [19]. Since [19] does not provide the construction, we describe it for sake of completeness. The auxillary graph $H$ contains a vertex $v_e$ for each edge $e\in E(G_{\downarrow })$. Moreover, two vertices $v_{e_1}$ and $v_{e_2}$ of $H$ are adjacent if and only if $e_1\cap e_2\ne \mathrm{\varnothing }$ and there exists a snapshot $G_i$ where both edges $e_1$ and $e_2$ are active. Now, maximizing the number $z$ of edge-disjoint $P_3$ covered by the solution is equivalent to finding a maximum matching in $H$ which can be done in polynomial time [28]. $◀$

Theorem 3.6 implies that TPVC can be solved in polynomial time if $G_{\downarrow }$ is a path. Hence, our result generalizes a result of Hamm et al. [21, Thm. 5] who provided a polynomial-time algorithm for TVC if $G_{\downarrow }$ is a path.

We reduce from the NP-hard Rainbow Matching problem on properly edge-colored paths [27]. In this problem, the instance $(P,\varphi ,q)$ consists of a path $P$ with vertex set $\{v_1,\mathrm{\dots },v_n\}$, an edge coloring $\varphi :E(P)\to [c]$ for some $c\in \mathbb{N}$, and an integer $q$ and the question is whether there exists a matching of size at least $q$ such that all edges in the matching are assigned a different color.

Consider the temporal graph $𝒢$ with vertex set $V(𝒢):=V(P)$ and the following snapshots: For each color $i\in [c]$, we introduce one snapshot $G_i$, which contains exactly the edges colored with the corresponding color $i$. Furthermore, we add $n-2q$ additional empty snapshots and set $k:=n-q$ to obtain the Budget-TDS instance $(𝒢,k,b=1)$. By construction, the underlying graph is a path and the maximum snapshot degree is one since $\varphi$ is a proper edge coloring, that is, no two incident edges of $P$ have the same color.

Correctness: We show that $P$ has a rainbow matching of size at least $q$ if and only if $𝒢$ has a temporal dominating set $𝒮$ of size at most $k=n-q$ which does not exceed the budget of one in any of the snapshots.

($\Rightarrow$) Suppose $M$ is a rainbow matching of size $q$. For each color $i\in [c]$ and each edge $v_j{v}_{j+1}\in M$ with $\varphi (v_j{v}_{j+1})=i$ we add $(v_j,i)$ to $𝒮$. Note that these temporal vertices already dominate $2q$ vertices since $M$ is a matching. For the remaining $n-2q$ undominated vertices from $V(𝒢)$ we add isolated temporal vertices from the empty snapshots to $𝒮$ such that there is no conflict with the budget constraint. This can be done because $𝒢$ contains $n-2q$ empty snapshots. Finally, note that $𝒮$ dominates all vertices, has size $q+n-2q=n-q=k$ and contains at most one temporal vertex from each snapshot since $M$ is a rainbow matching.

($\Leftarrow$) Suppose that $𝒮$ is a solution to $(𝒢,k,b=1)$. Since the maximum snapshot degree is one, we know that every temporal vertex dominates at most two vertices. A solution of size $k=n-q$ needs to dominate all $n$ vertices, which implies that there exist $q$ temporal vertices in $𝒮$ which dominate in total $2q$ vertices. Each of these $q$ temporal vertices is incident to exactly one edge and therefore comes from a snapshot which corresponds to some color of the edge coloring $\varphi$. By adding all these edges to $M$, we obtain a rainbow matching of size at least $q$. As the $q$ temporal vertices dominate in total $2q$ vertices, it follows that $M$ is a matching. The rainbow property is a consequence of the budget restriction which implies that $𝒮$ contains no two vertices from the same snapshot and therefore no two edges of the same color are added to $M$. $◀$

We get almost the same hardness for Budget-TVC.

Hence Budget-TDS and Budget-TVC are strictly harder than TDS and TVC with respect to the structure of the underlying graph and with respect to the maximum snapshot degree. Moreover, since $G_{\downarrow }$ is a path in Theorem 3.8, we directly obtain that Budget-TVC remains NP-hard even if the maximum snapshot degree is two. This is in sharp contrast to TVC which is solvable in polynomial time if the maximum snapshot degree is two, see Theorem 3.6. We now show that the snapshot degree of 2 in Theorem 3.8 is necessary for the NP-hardness on paths.

Let $(𝒢,k,t,b)$ be a Budget-TPVC instance. Observe that since the maximum snapshot degree is one, each temporal vertex can cover at most one edge. Consequently, if , we have a no-instance. Moreover, since an optimal solution never contains both endpoints of an edge, it is safe to assume that $k=t$.

To solve the instance $(𝒢,k,k,b)$, we use a max-flow problem, which can be solved in polynomial time [20]. Let $H$ be a flow-network with source $s$ and target $z$. Moreover, $H$ has a vertex $s_i$ for each snapshot $G_i$ and a vertex $e$ for each edge $e\in E(G_{\downarrow })$. The source has an arc with capacity $b$ to each vertex $s_i$ corresponding to a snapshot. The vertex $s_i$ corresponding to snapshot $G_i$ has an arc with capacity one to edge $e\in E(G_{\downarrow })$ if $e$ can be covered in $G_i$. Finally, each vertex $e$ for each $e\in E(G_{\downarrow })$ has an arc to the target $z$ with capacity $1$.

We now show that $(𝒢,k,k,b)$ is a yes-instance of Budget-TPVC if and only if $H$ has a maximum flow of $k$.

$(\Rightarrow )$ Assume that $H$ has a maximum flow of value $k$. Since each vertex $e\in V(H)$ corresponding to an edge in $G_{\downarrow }$ has only one outgoing arc which has capacity one, there exists at most one vertex $s_i$ such that there is a flow of value 1 from $s_i$ to $e$. Now, since the maximum snapshot degree is 1, we let $(v,i)$ be a temporal vertex such that $v$ is one of the endpoints of the edge in $G_{\downarrow }$ corresponding to $e$. We now argue that the set $S$ of these temporal vertices is a solution for $(𝒢,k,k,b)$. By the above, each vertex in $S$ covers exactly one unique edge and by the construction of our flow-network $S$ contains at most $b$ temporal vertices from each snapshot. Furthermore, since the flow has value $k$, we obtain that $|S|=k$ and thus $S$ is a solution for $(𝒢,k,k,b)$.

$(\Leftarrow )$ Let $S$ be a solution for $(𝒢,k,k,b)$ where no edge is covered twice. Consequently, each vertex in $S$ covers exactly one edge and this edge is covered by no other vertex in $S$. More precisely, let $S_i\subseteq S$ be the temporal vertices contained in snapshot $i$. Note that $|S_i|\le b$. For each snapshot $i$, we let a flow with value $|S_i|$ flow from the source $s$ to vertex $s_i$. Since each vertex $v$ in $S$ covers a unique edge $e\in E(G_{\downarrow })$, we let a flow of value 1 flow from $S_i$ to each edge which is covered by a vertex in $S_i$. Clearly, these are $|S_i|$ many. Finally, we let a flow from each covered edge to the target $z$ with a value 1 flow. Consequently, $H$ has a flow with value $|S|=k$. $◀$

Let $(𝒢,k,t,b)$ be a Budget-TPDS-instance. We can assume $b=1$ by taking $b$ copies of each snapshot. Note that this increases the lifetime of the temporal graph by the factor $b$.

Consider the following randomized algorithm. Let $\varphi :V(𝒢)\to [t]$ be a uniformly at random coloring of the vertices $V(𝒢)$. We say that a temporal vertex $(v,i)$ dominates the color $q$ if there exists a neighbor of $v$ in $G_i$ with color $q$. With $C_{v,i}$ we denote the set of colors, which are dominated by the temporal vertex $(v,i)$. For each set of colors $X\subseteq [t]$ and each $i\in [0,T]$ let

We initialize the table by setting $\mathrm{DP}[\mathrm{\varnothing },0]=0$ and $\mathrm{DP}[X,0]=\mathrm{\infty }$ for all $\mathrm{\varnothing }\ne X\subseteq [t]$. The remaining entries are computed recursively by

We prove the correctness by showing two inequalities.

($\ge$) Suppose that $𝒮$ is a set of temporal vertices for which the minimum in the definition of $\mathrm{DP}[X,i]$ is attained. Due to the minimizing, it is clear that each temporal vertex from $𝒮$ dominates at least one color from $X$. If $𝒮$ contains a temporal vertex $(v,i)$ from $G_i$, then $𝒮\setminus \{(v,i)\}$ is considered in the definition of the entry $\mathrm{DP}[X\setminus C_{v,i},i-1]$. Otherwise $𝒮$ is considered in the definition of $\mathrm{DP}[X,i-1]$. Therefore the inequality holds.

($\le$) Note that each set $𝒮$ which is considered in the definition of $\mathrm{DP}[X,i-1]$ is also considered in the definition of $\mathrm{DP}[X,i]$. Hence, we have $\mathrm{DP}[X,i]\le \mathrm{DP}[X,i-1]$. Now suppose the minimum on the right hand side of the computation is attained for the entry $\mathrm{DP}[X\setminus C_{v,i},i-1]$ and the set $𝒮$. Then clearly $𝒮\cup \{(v,i)\}$ is considered in the definition of $\mathrm{DP}[X,i]$ and we have $\mathrm{DP}[X,i]\le \mathrm{DP}[X\setminus C_{v,i},i-1]+1$. This proves the inequality.

Finally, the algorithm returns yes if and only if $\mathrm{DP}[\{1,\mathrm{\dots },t\},T]\le k$. This means, it returns yes if and only if there is a temporal vertex set of size at most $k$ which dominates $t$ pairwise differently colored vertices.

If we run this algorithm once, then it is not guaranteed that the random coloring $\varphi$ colors $t$ vertices, which are dominated by some solution of the Budget-TPDS-instance, with $t$ different colors. For derandomization we can iterate over a specific set of colorings, instead of randomly coloring the vertices. The set of colorings needs to contain at least one coloring which colors the “correct” $t$ vertices with $t$ distinct colors. Such a set can be constructed by using the definition of perfect hash families (see Proposition 4.1).

For a fixed coloring $\varphi$, the size of the table is $𝒪(2^t\cdot T)$ and it takes $𝒪(n^{2}T)$ time to compute one entry, which implies an overall running time of $𝒪(2^t\cdot n^2{T}^2)$ if the budget equals one. If we take $b$ copies of each snapshot, such that we can assume $b=1$, then the lifetime increases by the factor $b$ and consequently the running time is $𝒪(2^t\cdot n^2{T}^2{b}^2)$ for a fixed coloring $\varphi$.

Using the construction mentioned in Proposition 4.1 and running the algorithm from above for each coloring of this construction, we obtain an overall running time of ${(2e)}^t{t}^{𝒪(\log t)}\cdot n^3(\log n)b^2{T}^2$. $◀$

The algorithm of Theorem 4.2 also works analogously for Budget-TPVC: We only need to color the edges instead of the vertices. Hence, we obtain the following.

Recall that ${\mathrm{\Delta }}_{\max }(𝒢)\le \mathrm{\Delta }(G_{\downarrow })$ is the maximum snapshot degree. Observe that if $t>k\cdot ({\mathrm{\Delta }}_{\max }(𝒢)+1)$ for the TDS variants and if $t>k\cdot {\mathrm{\Delta }}_{\max }(𝒢)$ for the TVC variants, then we have a no-instance. Thus, we obtain the following.

Furthermore, recall that TDS is $\mathrm{W}[2]$-hard with respect to the solution size $k$ and that it is NP-hard even if $\mathrm{\Delta }(𝒢)=3$ [38]. Consequently, both parameters $k$ and $\mathrm{\Delta }(𝒢)$ are necessary to obtain an FPT-algorithm.

Of course, we would like to replace ${\mathrm{\Delta }}_{\max }(𝒢)\le \mathrm{\Delta }(G_{\downarrow })$ by potentially smaller parameters. However, since TVC and TDS are W[2]-hard with respect to $k$ if $G_{\downarrow }$ is a star, we cannot make use of degree-based parameterizations of $G_{\downarrow }$ such as the $h$-index of $G_{\downarrow }$ or the $c$-closure [16] of $G_{\downarrow }$. To circumvent this problem we consider the $h$-index of the temporal graph $𝒢$, which we defined as the maximum number $h(𝒢)$ such that $𝒢$ contains at least $h(𝒢)$ temporal vertices of degree at least $h(𝒢)$.

The idea for the algorithm is to first branch on the temporal vertices that have a high degree and then use the fact that after removing these vertices, the remaining instance has bounded maximum snapshot degree which allows us to use an FPT-algorithm for $t\le k\cdot {\mathrm{\Delta }}_{\max }$.

We only state the proof for Budget-TPDS, the proof for Budget-TPVC follows analogously. Let $I=(𝒢,k,t,b)$ be an instance of Budget-TPDS.

Let $Z$ be the set of temporal vertices of degree at least $h(𝒢)+1$. By definition, $|Z|\le h(𝒢)$. The idea is to first branch on the high-degree temporal vertices $Z$ whether they are part of a fixed solution $𝒮$ or not and then to use an adaption of the color coding algorithm described in Theorem 4.2 for an auxiliary Budget-TPDS instance $I^{\prime }$.

Now, let $𝒮$ be a fixed solution of $I$. Initially, we branch for each temporal vertex $(v,i)\in Z$ whether $(v,i)$ is part of $𝒮$ or not. Note that these are $2^{|Z|}\le 2^{h(𝒢)}$ possibilities. Next, consider a fixed possibility and let $Z_{\text{in}}:=Z\cap 𝒮$ and $Z_{\text{out}}:=Z\setminus 𝒮$. Now, let $t^{\prime }:=t-|V(N[Z_{\text{in}}])|$. Since each temporal vertex which is not in $Z$ can dominate at most $h(𝒢)+1$ temporal vertices, if $t^{\prime }>k\cdot (h(𝒢)+1)$ then this choice of $Z$ cannot lead to a solution. If for no choice of $Z$ we obtain $t^{\prime }\le k\cdot (h(𝒢)+1)$ then $I$ is a no-instance. Thus, in the following we assume that we consider a choice of $Z$ such that $t^{\prime }\le k\cdot (h(𝒢)+1)$. Moreover, by $a_i$ we denote the number of temporal vertices of $Z_{\text{in}}$ of snapshot $i$. If $a_i>b$ for any $i\in [T]$, then we abort this choice of $Z_{\text{in}}$ and $Z_{\text{out}}$ since we can pick at most $b$ temporal vertices of each snapshot. Thus, in the following we can safely assume that $a_i\le b$ for each $i\in [T]$. Now, let $b_i:=b-a_i$. By our assumption on $a_i$, we have $b_i\ge 0$ for each $i\in [T]$.

Next, we solve an auxiliary Budget-TPDS instance $I^{\prime }=(\mathscr{H},k^{\prime },t^{\prime },b^{\prime })$. Here, the temporal graph $\mathscr{H}$ has $b_i$ copies of snapshot $G_i$ for each $i\in [T]$. These are $T^{\prime }={\sum }_{i\in [T]}{b}_i$ snapshots in total. Note that $h(\mathscr{H})$ might be much higher than $h(𝒢)$. Moreover, we set $b^{\prime }:=1$ and $k^{\prime }:=k-|Z_{\text{in}}|$.

Next, we use color coding with $t^{\prime }+1$ colors on $V(\mathscr{H})=V(𝒢)$ to determine the set ${𝒮}^{\prime }:=𝒮\setminus Z_{\text{in}}$ as follows: The color $t^{\prime }+1$ is only used for the vertices in $V(N[Z_{\text{in}}])$ and consequently, in each uniformly at random coloring with the first $t^{\prime }$ colors we only color the vertices $V(\mathscr{H})\setminus V(N[Z_{\text{in}}])$. Again, we say that a temporal vertex $(v,i)$ dominates the color $q\in [t^{\prime }]$ if there exists a neighbor of $v$ in snapshot $H_i$ with color $q$. Now, the table $\mathrm{DP}[X,i]$ for a set of colors $X\subseteq [t^{\prime }]$ and each $i\in [0,T]$ is defined similar to Theorem 4.2, that is:

We initialize the table analogously to the proof of Theorem 4.2, by setting $\mathrm{DP}[\mathrm{\varnothing },0]=0$ and $\mathrm{DP}[X,0]=\mathrm{\infty }$ for all $\mathrm{\varnothing }\ne X\subseteq [t]$.

We again denote by $C_{v,i}$ the set of colors, which are dominated by the temporal vertex $(v,i)$. The remaining entries are then computed recursively by

Hence, the only change to the update in Theorem 4.2 is that we no do not consider temporal vertices of $Z_{\text{out}}$. The correctness of the dynamic program follows since we assign all vertices in $V(N[Z_{\text{in}}])$ color $t^{\prime }+1$ to indicate that they are already dominated. Since in the $\mathrm{DP}$ we only consider color subsets $X\subseteq [t^{\prime }]$, we cannot pick any vertex of $Z_{\text{in}}$ again in the dynamic program. Moreover, during the updates of the dynamic program we do not pick any vertex of $Z_{\text{out}}$. Consequently, $𝒮:=\widehat{𝒮}\cup Z_{\text{in}}$ is a solution for $I$, where $\widehat{𝒮}=\{(v,i):(v,i^{\prime })\in {𝒮}^{\prime },\text{ snapshot }{i}^{\prime }\text{ of }\mathscr{H}\text{ is a copy of snapshot }i\text{ in }𝒢\}$.

For the running time, observe that there are $2^{h(𝒢)}$ possibilities for $Z_{\text{in}}$ and $Z_{\text{out}}$. Moreover, the running time of the dynamic program is ${(2e)}^{t^{\prime }}t_{}^{\prime }{}_{}{}^{𝒪(\log t^{\prime })}\cdot n^3(\log n)b^2{T}^2$. Since we only use the dynamic program if $t^{\prime }\le k\cdot (h(𝒢)+1)$, we obtain an overall running time of $2^{h(𝒢)}{(2e)}^{k\cdot (h(𝒢)+1)}k\cdot {(h(𝒢)+1)}^{𝒪(\log (k\cdot (h(𝒢)+1)))}\cdot n^3(\log n)b^2{T}^2$. $◀$