Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis

To the best of our knowledge, our introduced problem WTR has not yet been studied.

One framework that is conceptually related to the idea of repairing given schedules is the approach of parameterized local search: The idea is to apply a limited number of changes on a given schedule to improve a target function value. Balzereit et al. [3] study parameterized local search for a single machine scheduling problem. While their approach mostly serves as a subroutine in a hill-climbing setting, it can also be used to repair schedules.

Another framework related to repairing schedules is reoptimization [17, 4]: The idea of reoptimization is to compute approximate solutions of perturbed instances from given optimal solutions of an original instance. There are constant factor approximations for reoptimization settings of multi-machine makespan minimization under the constraint that some jobs are not allowed to be scheduled parallel [17]. Boria and Della Croce [4] provide constant factor approximizations for multiple min-sum scheduling problems with release dates.

We initiate the theoretical study of WTR. As WTR is NP-hard even if the number of allowed waiting time removals is unbounded (Theorem 3), the problem is inapproximable, motivating our parameterized complexity analysis. Considering the most natural parameterizations (by the number $n$ of jobs, the number $k$ of deletions, the time horizont $T$, and the alphabet size $|\mathrm{\Sigma }|$ and combinations thereof), we derive a complete picture of the parameterized complexity of WTR. An overview of the results is shown in Table 1.

Notably, while most of our hardness results hold already for alphabets of constant size, the paraNP-hardness of WTR parameterized by $T$ (Theorem 6) is contrasted with the fixed-parameter tractability with respect to $T+|\mathrm{\Sigma }|$ (Theorem 7). A further notable result is that parameterizing with the number $n$ of jobs is not sufficient to ensure fixed-parameter tractability (Theorem 3), but only results in an XP-algorithm (Theorem 4).

Recall that we aim to study a problem where the goal is to adjust a given plan by removing waiting times. In the following, we formalize this idea.

Let $\mathrm{\Sigma }$ be a finite alphabet, let $x\notin \mathrm{\Sigma }$, and let $T\in \mathbb{N}$ be a number of time steps. A $T$-step capacity bound for $\mathrm{\Sigma }$ is a mapping $c:\mathrm{\Sigma }\times [1,T]\to {\mathbb{N}}_0$. Intuitively, $c(\sigma ,t)$ corresponds to the capacity of symbol $\sigma$ at time step $t$. A job $(w,s)$ is a tuple consisting of a string $w\in {(\mathrm{\Sigma }\cup \{x\})}^{\ast }$ and a starting time $s\in \mathbb{N}$ that satisfies $s+|w|-1\le T$. Intuitively, the inequality guarantees that every job is completed by time step $T$. Given a set of jobs $𝒥:=\{(w_i,s_i)\mid i\in [1,n]\}$, a symbol $\sigma \in \mathrm{\Sigma }$ and a time step $t\in [1,T]$, we define the load of symbol $\sigma$ at time step $t$ as

A set $𝒥$ of jobs satisfies the capacity constraints $c$ if ${\lambda }_{\sigma }^t\le c(\sigma ,t)$ for every combination of $\sigma \in \mathrm{\Sigma }$ and $t\in [1,T]$. For a job $J$ and some $t\in [s,s+|J|-1]$, we say that the $(t-s+1)$th letter of $J$ is processed at time $t$.

Given a set of jobs $𝒥:=\{(w_i,s_i)\mid i\in [1,n]\}$, we let $\mathrm{\#}{x}_i$ denote the number of occurrences of the symbol $x$ in the string $w_i$ for $i\in [1,n]$. The problem WTR is defined as follows.

Waiting Time Removal (WTR)

Input:

A number of time steps $T$, a set $𝒥:=\{(w_i,s_i)\mid i\in [1,n]\}$ of jobs, a $T$-step capacity bound $c$, and an integer $k$.

Question:

Does there exist a family of sets $R_1,\mathrm{\dots },R_n$ with $R_i\subseteq [1,\mathrm{\#}{x}_i]$ for each $i\in [1,n]$ and ${\sum }_{i=1}^n|R_i|\le k$ such that the job set ${𝒥}^{\prime }:=\{(w_i-R_i,s_i)\mid i\in [1,n]\}$ satisfies the capacity constraints $c$?

For notational convenience, we define for a job $J=(w,s)$ its length $|J|:=|w|$, its starting time $s(J):=s$, and $J-R:=(w-R,s)$ for $R\subseteq [1,\mathrm{\#}{x}_i]$.

Note that $T\cdot n$ essentially bounds the size of an instance $(T,𝒥,c,t)$ of WTR: Each $w_i$ has length at most $T$ and thus, $|𝒥|$ can be encoded by encoding at most $T\cdot n$ symbols. Moreover, the load of a symbol can never exceed $n$ and thus, $c$ can be encoded using $𝒪(T^2\cdot n\log (n))$ bits. Therefore, we can observe the following.

Furthermore, note that WTR can be solved by the following simple brut-force algorithm: Enumerate all size-$k$ subsets of occurrences of the symbol $x$ in the input instance, and check whether removing precisely these occurrences provides a modified set ${𝒥}^{\prime }$ that satisfies the capacity constraints $c$. This simple brute-force strategy implies the following.

We use standard notation from graph theory, see e.g. [12]. More precisely, all appearing graphs are undirected unless stated otherwise. A graph $G=(V,E)$ is $k$-partite if its vertex set can be partitioned into $k$ independent sets, i.e., $V=V_1\cup \mathrm{\dots }\cup V_k$ with $V_i\cap V_j=\mathrm{\varnothing }$ for each $i\ne j$ and for each set $V_i$, there is no edge whose endpoints are both contained in $V_i$. For a graph $G=(V,E)$ and $V_1,V_2\subseteq V$, we denote by $E[V_1,V_2]$ the edges with one endpoint in $V_1$ and the other endpoint in $V_2$. For a vertex $v\in V$, we denote by $\delta (v)$ the set of edges incident to $v$.

We reduce from Multicolored Independent Set which is NP-hard [11] and W[1]-hard parameterized by solution size $\mathrm{\ell }$ [15]. In Multicolored Independent Set, one is given an $\mathrm{\ell }$-partite graph $G=(V_1\cup \mathrm{\dots }\cup V_{\mathrm{\ell }},E)$ with $|V_1|=|V_2|=\mathrm{\dots }=|V_{\mathrm{\ell }}|$, and the task is to find a multicolored independent set, i.e., a set of $\mathrm{\ell }$ pairwise non-adjacent vertices containing exactly one vertex from each $V_i$. Let $G=(V_1\cup \mathrm{\dots }\cup V_{\mathrm{\ell }},E)$ be an instance of Multicolored Independent Set. We fix an arbitrary ordering $e_1,\mathrm{\dots },e_m$ of the edges of $G$ as well as of the vertices of each color class $V_i=\{v_i^1,\mathrm{\dots },v_i^{|V_1|}\}$. For each color class $V_i$ and each edge $e_p\in E$, we define the $|V_1|$-letter substring $w_i^p$ to be

Using these substrings, we create, for each $i\in [1,\mathrm{\ell }]$, one job $J_i=(w_i,1)$ where

We define the $(m\cdot |V_1|+|V_1|-1)$-capacity bound $c$: For every $p\in [1,m]$, letter 1 has capcity one at time $p\cdot |V_1|$. All other capacities are infinite. See Figure 2 for an example.

The reduction clearly runs in polynomial time and the number of jobs equals $\mathrm{\ell }$.

We continue by showing correctness. First note that for any set $R_i\subseteq [1,|V_1|-1]$, job $J_i-R_i$ contributes to the load of letter 1 at time $p\cdot |V_1|$ if and only if $v_i^{|R_i|+1}$ is adjacent to $e_p$. Given a multicolored independent set $I=\{v_1^{j_1},\mathrm{\dots },v_{\mathrm{\ell }}^{j_{\mathrm{\ell }}}\}$, we construct a deletion set $ℛ=\{R_1,\mathrm{\dots },R_n\}$ as follows: For each job $J_i$, we let $R_i=[1,j_i-1]$. To see that this $\{(w_i-R_i,1)\mid i\in [1,n]\}$ satisfies the capacity constraints, note that only letter $1$ has a finite capacity (at times $t=p\cdot |V_1|$ for $p\in [1,m]$), so it suffices to show that the load of letter $1$ does not exceed its capacity. Assume towards a contradiction that there is some time $t$ where the load of letter $1$ exceeds its capacitiy, i.e., $t=p\cdot |V_1|$ for some $p\in [1,m]$ and there are two jobs $J_i-R_i$ and $J_{i^{\prime }}-R_{i^{\prime }}$ both contributing to the load of $1$ at time $t$. This implies that $e_p$ is incident to both $v_i^{j_i}$ and $v_{i^{\prime }}^{j_{i^{\prime }}}$, a contradiction to $I$ being an independent set.

We conclude with the reverse direction, so let $ℛ=\{R_1,\mathrm{\dots },R_n\}$ be a deletion family satisfying the capacity constraints. Let $j_i:=|R_i|\in [1,|V_1|-1]$. We claim that $I=\{v_1^{j_1},\mathrm{\dots },v_{\mathrm{\ell }}^{j_{\mathrm{\ell }}}\}$ is an independent set. Assume towards a contradiction that $e_p=\{v_i^{j_i},v_{i^{\prime }}^{j_{i^{\prime }}}\}$ for some $p\in [m]$ and $i,i^{\prime }\in [1,\mathrm{\ell }]$. Then at time $p\cdot |V_1|$, both $J_i-R_i$ and $J_{i^{\prime }}-R_{i^{\prime }}$ contribute to the load of letter $1$, a contradiction to the feasibility of the schedule. $◀$

While WTR is presumably not fixed-parameter tractable for $n$, we show that – on the positive side – WTR can be solved in polynomial time for constant values of $n$ by providing the following XP algorithm.

We give a dynamic program solving the problem. The dynamic programming table $\tau$ has entries of the form $\tau [(t,p_1,\mathrm{\dots },p_n)]$ for every suitable tuple $(t,p_1,\mathrm{\dots },p_n)$, where we call $(t,p_1,\mathrm{\dots },p_n)$ with $t\in [0,T+1]$ and $p_i\in [0,|J_i|+1]$ for each $i\in [1,n]$ suitable if, for every $i\in [n]$, it holds that $p_i=0$ if and only if . Each entry stores the minimum size of a deletion set such that the load of any symbol for any time $t^{\prime }\le t$ does not exceed its capacity and at time $t$ (where each letter has capacity 0 for $t^{\prime }\in \{0,T+1\}$), the $p_i$th letter of $J_i$ is processed. Herein, $p_i=0$ encodes that no letter of $J_i$ is processed until time $t$ and $p_i=|J_i|+1$ encodes that all letters from $J_i$ have already been processed until time $t$. The table is computed as follows: We initialize the table by setting

For the update step, we introduce some additional notation. We say that a suitable tuple $(t-1,p_1^{\prime },\mathrm{\dots },p_n^{\prime })$ is compatible with a suitable tuple $(t,p_1,\mathrm{\dots },p_n)$ if, for every $i\in [n]$,

• $\mathrm{■}$

  $p_i^{\prime }\le p_i$,

• $\mathrm{■}$

  if $p_i\notin \{0,|J_i|+1\}$, then and $w_i[p_i^{\prime }+1]=w_i[p_i^{\prime }+2]=\mathrm{\dots }=w_i[p_i-1]=x$, and

• $\mathrm{■}$

  for each $\sigma \in \mathrm{\Sigma }$, we have $|\{i\mid s_i[p_i]=\sigma \}|\le {\lambda }_{\sigma }^t$.

Intuitively, this means that if the $p_i^{\prime }$th letter of job $J_i$ is processed at time $t-1$, then the $p_i$th letter can be processed at time $t$ (after deleting all $x$ in between; the second item ensures that only $x$ are in between the $p_i^{\prime }$th and $p_i$th letter). We update the table as follows:

An optimal solution can be read from $\tau [(T+1,|J_1|+1,\mathrm{\dots },|J_n|+1)]$ using traceback. More formally, we have a yes-instance of WTR if and only if $\tau [(T+1,|J_1|+1,\mathrm{\dots },|J_n|+1)]\le k$.

The dynamic programming table has $O(T\cdot {\mathrm{\Pi }}_{i=1}^n(|J_i|+2))=O(T^{n+1})$ entries, each of which can be computed in $O(n\cdot T^n)$ time. Thus, the dynamic program runs in $O(n\cdot T^{2n+1})$ time.

It remains to show correctness. First, we show by induction on $t$ that if , then there is a deletion family of size $q$ such that no load exceeds its capacity at any time $t^{\prime }\le t$ and at time $t$, the $p_i$th letter of $J_i$ is scheduled. This clearly holds for $t=0$. For $t\ge 1$, let $a:=(t-1,p_1^{\prime },\mathrm{\dots },p_n^{\prime })$ such that $\tau [(t,p_1,\mathrm{\dots },p_n)]=\tau [a]+{\sum }_{i:p_i\ne p_i^{\prime }}(p_i-p_i^{\prime }-1)$. This entry $\tau [a]$ corresponds to a deletion family ${ℛ}^{\prime }$. By induction, for jobs $\{J_i-R_i^{\prime }\}$, no load is exceeded for any time . By the second condition, the $p_i^{\prime }+1,\mathrm{\dots },p_i-1$th letters of $J_i$ are all $x$, say the $r_i$th to $r_i^{\prime }$th occurrences of $x$. Setting $ℛ=\{R_i^{\prime }\cup [r_i,r_i^{\prime }]\mid i\in [n]\}$ for each $i\in [n]$ results in a deletion family of size $\tau [a]+{\sum }_{i:p_i\ne p_i^{\prime }}(p_i-p_i^{\prime }-1)=q$. By the third condition, no load is exceeded at time $t$. By induction, no load is exceeded at any time $t^{\prime }\le t-1$ for ${ℛ}^{\prime }$; consequently, also for $ℛ$ no load is exceeded at any time $t^{\prime }\le t-1$ for $ℛ$. Thus, $ℛ$ is a deletion family of size $q$ with the desired properties.

Next, we show that if there is a deletion family $ℛ$ of size $q$ such that at time $t$, for each $i\in [1,n]$ the $p_i$th letter of $J_i$ is scheduled, and no load is exceeded for any $t^{\prime }\le t$, then $\tau [(t,p_1,\mathrm{\dots },p_n)]\le q$. We again do so by induction on $t$. For $t=0$, the statement is obvious, so consider $t>0$. The deletion family $ℛ$ is also a deletion family where at time $t-1$, the $p_i^{\prime }$th letter of $J_i$ is scheduled for some $p_1^{\prime },\mathrm{\dots },p_n^{\prime }$. By the second condition, the $p_i^{\prime }+1,\mathrm{\dots },p_i-1$th letters of $J_i$ are all $x$, say the $r_i$th to $r_i^{\prime }$th occurrences of $x$. Setting $R_i^{\prime }:=R_i\setminus [r_i,r_i^{\prime }]$ for $i\in [1,n]$ therefore results in a deletion set ${ℛ}^{\prime }=\{R_1^{\prime },\mathrm{\dots },R_n^{\prime }\}$ of size $q-{\sum }_{i:p_i\ne p_i^{\prime }}(p_i-p_i^{\prime }-1)$. By induction, we have ${\sum }_{i=1}^n|R_i^{\prime }|\ge \tau [(t-1,p_1^{\prime },\mathrm{\dots },p_n^{\prime })]$. Thus, we have

The correctness follows. $◀$

Adding a simple pruning rule to the dynamic program from Theorem 4 yields fixed-parameter tractability by the combined parameter $n+k$:

For every job $J_i=(w_i,s_i)$, the deletion set $R_i$ has size at most $k$. Thus, at each time $t$, at most $k$ different letters from $w_i$ can be scheduled, implying that at most $k$ different values for $p_i$ need to be considered. Consequently, the number of DP entries to consider is $O(T\cdot n^k)$, and each of these entries can be computed in $O(n\cdot n^k)$ time. Therefore, WTR can be solved in $O(T\cdot n^{2k+1})$ time. $◀$

We provide a reduction from Independent Set. In Independent Set, one is given a graph $G=(V,E)$ together with an integer $\mathrm{\ell }$. The question is whether there exists a set $I\subseteq V$ of pairwise non-adjacend vertices with $|I|\ge \mathrm{\ell }$. Independent Set is well-known to be NP-hard even if $G$ has maximum degree $3$ [7].

Let $(G=(V,E),\mathrm{\ell })$ be an instance of Independent Set, where $G$ has maximum degree $3$. We describe how to construnct an equivalent instance of WTR in polynomial time. To this end, we assume that $G$ has a proper edge coloring with four colors: Due to Vizing’s Theorem [23], we can partition the edge set $E$ into four sets $E_1$, $E_2$, $E_3$, and $E_4$ such that for each $i\in [1,4]$, no two edges in $E_i$ share one endpoint. Since the proof of Vizing’s Theorem provides an algorithm computing the partition in polynomial time, we may use the sets $E_1,\mathrm{\dots },E_4$ for our construction.

To construct an instance $(T,𝒥,c,k)$ of WTR, we first set $k:=\mathrm{\ell }$ and we set $T:=10$. Furthermore, we define the alphabet $\mathrm{\Sigma }:=\{0\}\cup E$. Next, given some $v\in V$ and some $i\in [1,4]$, we let $w_v^i:=00$ if $v$ has no incident edge in $E_i$, and we let $w_v^i:=0e$ otherwise, where $e$ is the unique incident edge in $E_i$. We then define $w_v:=x\circ w_v^1\circ w_v^2\circ w_v^3\circ w_v^4\circ 0$ and set $𝒥:=\{(w_v,1)\mid v\in V\}$. Note that for every $v\in V$, we have $|w_v|=10$.

We complete the construction by defining the capacity $c$. We set $c(0,10):=|V|-\mathrm{\ell }$. Furthermore, for every $i\in \{2,4,6,8\}$ and $e\in E$ we define $c(e,i):=1$. All remaining capacities are set to $\mathrm{\infty }$.

Before we prove the correctness, we provide some intuition. Since $c(0,10)=|V|-\mathrm{\ell }$ and every $w_v$ ends with the symbol $0$ at time step $10$, we need to remove the unique occurrence of $x$ in $\mathrm{\ell }$ strings, which then corresponds to the choice of vertices in a solution of Independent Set. The capacities $c(e,i):=1$ for $i\in \{2,4,6,8\}$ then guarantee that no pair of chosen vertices are incident with the same edge.

We conclude the proof by showing that $(G,\mathrm{\ell })$ is a yes-instance of Independent Set if and only if $(T,𝒥,c,k)$ is a yes-instance of WTR.

Let $(G,\mathrm{\ell })$ be a yes-instance of Independent Set. Then, there is a set $I\subseteq V$ containing $\mathrm{\ell }$ vertices that are pairwise non-adjacent. We construct a solution of the WTR instance as follows: for each $v\in I$, we remove the unique occurrence of $x$ in $w_v$ and let ${\tilde{w}}_v$ denote the resulting string. Note that ${\tilde{w}}_v[t]=w_v[t+1]$ for $t\in [1,9]$. Note that we removed $|I|=\mathrm{\ell }=k$ occurrences of $x$. We show that the modified job set satisfies the capacity constraints $c$: First, observe that ${\lambda }_0^{10}=|V|-|I|=V-\mathrm{\ell }=c(0,10)$. Second, let $i\in \{2,4,6,8\}$ and assume towards a contradiction that $c(e,i)\ge 2$ for some symbol $e\in \mathrm{\Sigma }$. Then, there exist ${\tilde{w}}_v$ and ${\tilde{w}}_u$ with ${\tilde{w}}_v[i]={\tilde{w}}_u[i]=e$. Then, we have $w_v[i+1]=w_u[i+1]=e$ and thus, by the construction of $𝒥$, the vertices $v$ and $u$ are both incident with the same edge $e$ in $G$. This contradicts the fact that $I$ consists of pairwise non-adjacent vertices. Consequently, we have $c(e,i)\le 1$ for every $i\in \{2,4,6,8\}$ and $e\in E$. Since all other capacities are $\mathrm{\infty }$, we conclude that the modified job set satisfies the capacity constraints $c$ and thus, $(T,𝒥,c,k)$ is a yes-instance of WTR.

Conversely, let $(T,𝒥,c,k)$ be a yes-instance of WTR. Then, there is a subset of jobs ${𝒥}^{\prime }\subseteq 𝒥$ with $|{𝒥}^{\prime }|\le k=\mathrm{\ell }$ such that removing the unique occurrence of $x$ in the corresponding strings results in a plan that satisfies the capacity constraints $c$. Observe that $|{𝒥}^{\prime }|=\mathrm{\ell }$ since otherwise ${\lambda }_0^{10}=|V|-|{𝒥}^{\prime }|>|V|-\mathrm{\ell }=c(0,10)$. Let $w_{v_1},\mathrm{\dots },w_{v_{\mathrm{\ell }}}$ be the strings of the jobs in ${𝒥}^{\prime }$. Then, $I:=\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$ is a set of vertices of $G$ with $|I|=\mathrm{\ell }$. It reamins to show that the vertices in $I$ are pairwise non-adjacent. Assume towards a contradiction that two vertices $v_1$ and $v_2$ of $I$ are connected by an edge $e$. Recall that the edge set $E$ is partitioned into the sets $E_1,\mathrm{\dots },E_4$. Without loss of generality we assume $e\in E_1$. Then, by the construction of the jobs we have $w_{v_1}[3]=w_{v_2}[3]=e$. Removing the single occurrence of $x$ in $w_{v_1}$ and $w_{v_2}$ provides strings ${\tilde{w}}_{v_1}$ and ${\tilde{w}}_{v_2}$ with ${\tilde{w}}_{v_1}[2]={\tilde{w}}_{v_2}[2]=e$. Since $c(e,2)=1$, this contradicts the fact that the modified job set satisfies the capacity constraints $c$. Consequently, all vertices in $I$ are pairwise non-adjacent and thus, $(G,\mathrm{\ell })$ is a yes-instance of Independent Set. $◀$

Note that the alphabet size of the instance constructed in the proof of Theorem 6 is roughly the size of the input graph of the Independent Set instance. Recall that in our application the symbols in $\mathrm{\Sigma }$ correspond to distinct machine types on which the jobs need to be processed. In a real-world production setting it is reasonable that there are only few distinct machines types. Motivated by this observation, we study the combined parameter $T+|\mathrm{\Sigma }|$ and show that WTR is FPT for this parameterization.

Let $(T,𝒥,c,k)$ be an instance of WTR. We show fixed-parameter tractability by reformulating WTR as an integer linear program (ILP) where the number of variables is bounded by a function only depending on $T$ and $|\mathrm{\Sigma }|$. It is well-known that ILP parameterized by the number of variables is in FPT [9]. To this end, we introduce the notion of job types. Recall that a job $(w,s)\in 𝒥$ consists of a string $w\in {(\mathrm{\Sigma }\cup \{x\})}^{\ast }$ and a starting time $s\in [1,T]$. We say that two jobs have the same type $\tau =(w_{\tau },s_{\tau })$ if they have the same string $w_{\tau }$ and the same starting time $s_{\tau }$. We denote the number of jobs of type $\tau$ by $n_{\tau }$. For each job type $\tau$, we consider possible $x$-removal sets $R\subseteq [1,\mathrm{\#}{w}_{\tau }]$. We provide the ILP formulation by specifying the variables, the constraints, and the target function.

For each combination of a job type $\tau$ and a possible removal set $R\subseteq [1,\mathrm{\#}{w}_{\tau }]$, we introduce an integer variable $Y_{(\tau ,R)}$. The intuitive idea is that the value of $Y_{(\tau ,R)}$ equals the number of jobs with type $\tau$ whose internal $x$-deletions correspond to the (possibly empty) removal set $R$. More precisely, a solution set ${𝒥}^{\prime }$ contains exactly $Y_{(\tau ,R)}$ jobs of the form $(w_{\tau }-R,s_{\tau })$.

For each type $\tau$, we add the following constraint, ensuring that all jobs of type $\tau$ are scheduled:

For each combination of $\sigma \in \mathrm{\Sigma }$ and $t\in [1,T]$, we introduce the following constraint:

The left-hand side corresponds to the load of symbol $\sigma$ at time step $t$. Thus, these constraints guarantee that the solution satisfies the capacity constraints $c$: Intuitively, each string $w_{\tau }$ has been modified by a (possibly empty) $x$-removal set $R$. For a given type $\tau$, the inner sum counts all modified strings of type $\tau$ that have symbol $\sigma$ at time step $t$. Since we sum up these values over all possible types, the left-hand side corresponds to the load of symbol $\sigma$ at time step $t$.

The target function has the form

Recall that intuitively each value of $Y_{(\tau ,R)}$ equals the number of jobs with type $\tau$ whose internal $x$-deletions correspond to the (possibly empty) removal set $R$. Thus, for each combination of a type $\tau$ and a removal set $R$, we delete exactly $Y_{(\tau ,R)}\cdot |R|$ symbols. Since we sum up over all $\tau$ and $R$, the target function models the total number of $x$-deletions.

Note that the number of strings in ${(\mathrm{\Sigma }\cup \{x\})}^{\ast }$ in an instance with maximum time step $T$ is bounded by ${(|\mathrm{\Sigma }|+1)}^T$, and that we have at most $T$ starting positions. Consequently, there are at most $T\cdot {(|\mathrm{\Sigma }|+1)}^T$ possible job types $\tau =(w_{\tau },s_{\tau })$. Furthermore, since $|w_{\tau }|\le T$ for all $\tau$, there are at most $2^T$ possible $x$-removal sets $R\subseteq [1,\mathrm{\#}{w}_{\tau }]$. Thus, the number of variables $Y_{(\tau ,R)}$ is bounded by $T\cdot {(|\mathrm{\Sigma }|+1)}^T\cdot 2^T$. By a classical result by Lenstra [9], an ILP can be solved FPT-time with respect to the number of variables. This implies that the above ILP can be solved in FPT-time with respect to $T+|\mathrm{\Sigma }|$. $◀$

We complement the FPT result for $T+|\mathrm{\Sigma }|$ by showing that WTR is unlikely to admit a problem kernel of polynomial size for this parameterization.

We prove the statement by providing a polynomial parameter transformation from Set Cover. In Set Cover, one is given a universe of elements $U$, a familiy $ℱ\subseteq 2^U$ of subsets of $U$, and an integer $\mathrm{\ell }$. The question is whether there exists a subfamily ${ℱ}^{\prime }\subseteq ℱ$ such that $|{ℱ}^{\prime }|\le \mathrm{\ell }$ and ${\bigcup }_{F\in {ℱ}^{\prime }}F=U$. Set Cover parameterized by $|U|$ does not admit a polynomial kernel unless $\text{NP}\subseteq \text{coNP}/\text{poly}$ [6].

Let $(U,ℱ,\mathrm{\ell })$ be an instance of Set Cover and fix an arbitrary ordering $U:=\{u_1,\mathrm{\dots },u_{|U|}\}$ of the elements in the universe. We describe how to construct an equivalent instance $(T,𝒥,c,k)$ of WTR for the alphabet $\mathrm{\Sigma }=\{0,1\}$. We set $k:=\mathrm{\ell }$ and we set $T:=2\cdot |U|+1$. Note that $T$ is polynomial in $|U|$. Next, we define the job set $𝒥$. Given some $F\in ℱ$ and some $u\in U$, we let $w_u^F:=01$ if $u\in F$ and $w_u^F:=00$ if $u\notin F$. We define the job set $𝒥:=\{(w^F,1)\mid F\in ℱ\}$, where

Note that  $w_F[2i+1]=1$ if and only if $u_i\in F$ and we have $w_F[2i]=0$ for every $i\in [1,|U|]$.

We finish the construction by defining the $(2\cdot |U|+1)$-capacity bound $c$: For every $i\in [1,|U|]$, we set $c(1,2i+1):=|\{F\in ℱ\mid u\in F\}|-1$. All remaining $c(\sigma ,t)$ are set to $\mathrm{\infty }$.

We next show that $(U,ℱ,\mathrm{\ell })$ is a yes-instance of Set Cover if and only if $(T,𝒥,c,\mathrm{\ell })$ is a yes instance of WTR.

Let $(U,ℱ,\mathrm{\ell })$ be a yes-instance of Set Cover. Then, there exists a subfamily ${ℱ}^{\prime }\subseteq ℱ$ with $|{ℱ}^{\prime }|\le \mathrm{\ell }$ such that for each $i\in [1,|U|]$, there is one $F\in {ℱ}^{\prime }$ with $u_i\in F$. We construct a solution of the WTR instance as follows: for each $F\in {ℱ}^{\prime }$, we remove the unique occurrence of $x$ in $w^F$, and let ${\tilde{w}}^F$ denote the resulting string. Note that ${\tilde{w}}^F[t]=w^F[t+1]$ for every $t\in [1,T-1]$. We show that the modified job set satisfies the capacity constraints $c$. Since all other capacities are $\mathrm{\infty }$, it suffices to show that for each $i\in [1,|U|]$ the load of symbol $1$ at time step $2i+1$ is not larger than $c(1,2i+1)$. Since ${\tilde{w}}^F[2i+1]=w^F[2i+2]=0$ for all $F\in {ℱ}^{\prime }$, we have ${\lambda }_1^{2i+1}=|\{F\in ℱ\setminus {ℱ}^{\prime }\mid u_i\in F\}|$. Since each $u_i$ is contained in at least one $F\in {ℱ}^{\prime }$, we conclude that ${\lambda }_1^{2i+1}\le |\{F\in ℱ\mid u_i\in F\}|-1=c(1,2i+1)$. Therefore, $(T,𝒥,c,\mathrm{\ell })$ is a yes instance of WTR.

Conversely, let $(T,𝒥,c,k)$ be a yes-instance of WTR. Then, there is a subset ${𝒥}^{\prime }\subseteq 𝒥$ of jobs with $|{𝒥}^{\prime }|\le \mathrm{\ell }$ such that removing the unique occurrence of $x$ in the corresponding strings results in a plan that satisfies the capacity constraints $c$. Let $w^{F_1},\mathrm{\dots },w^{F_{|{𝒥}^{\prime }|}}$ be the strings of the jobs in ${𝒥}^{\prime }$. Then, ${ℱ}^{\prime }:=\{F_1,\mathrm{\dots },F_{|{𝒥}^{\prime }|}\}$ is a subfamily of $ℱ$ of size at most $\mathrm{\ell }$. Assume towards a contradiction that there is some $u_i\in U$ with $u_i\notin {\bigcup }_{F\in {ℱ}^{\prime }}F$. Then, for each $F\in ℱ$ with $u_i\in F$, the occurrence of $x$ in $w^F$ has not been removed. Consequently, the load of symbol $1$ at time step $2i+1$ is $|\{F\in ℱ\mid u_i\in F\}|>c(1,2i+1)$. This contradicts the fact that removing the $x$ in the strings of ${𝒥}^{\prime }$ results in a job set that satisfies the capacity constraints $c$. Therefore, $(U,ℱ,\mathrm{\ell })$ is a yes-instance of Set Cover. $◀$

The following two observations can be made by a taking closer look at the instance constructed in the proof of Theorem 8: First, the parameter $k$ equals the solution size of the Set Cover instance. Since Set Cover is known to be W[2]-hard when parameterized by solution size [5], this implies the following.

Second, the parameter $n+k$ is upper-bounded by $2\cdot |ℱ|$, where $ℱ$ is the set familiy in the Set Cover instance. Since Set Cover does not admit a polynomial kernel for $|ℱ|$ [6], this implies the following.

Next, consider the parameterization by $T+k$. Recall that WTR is XP for $k$ by Observation 2 and thus, WTR is XP for $T+k$. We complement this result by showing W[1]-hardness.

We reduce from Multicolored Clique parameterized by solution size $\mathrm{\ell }$. In Multicolored Clique, one is given an $\mathrm{\ell }$-partite graph $G=(V_1\cup \mathrm{\dots }\cup V_{\mathrm{\ell }},E)$ with $|V_1|=|V_2|=\mathrm{\dots }=|V_{\mathrm{\ell }}|$, and the task is to find a multicolored clique, i.e., a set of $\mathrm{\ell }$ pairwise adjacent vertices containing exactly one vertex from each $V_i$. Multicolored Clique is W[1]-hard parameterized by $\mathrm{\ell }$, even if there is some $r\in \mathbb{N}$ so that each vertex has exactly $r$ neighbors in every other color class [5]. Let $G=(V_1\cup \mathrm{\dots }\cup V_{\mathrm{\ell }},E)$ be an instance of Multicolored Clique where each vertex $v$ has exactly $r$ neighbors in every other color class. We let $f:[1,\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)]\to \left(\genfrac{}{}{0pt}{}{[1,\mathrm{\ell }]}{2}\right)$ be an arbitrary bijection to fix an ordering of the set $\left(\genfrac{}{}{0pt}{}{[1,\mathrm{\ell }]}{2}\right):=\{X\subseteq [1,\mathrm{\ell }]\mid |X|=2\}$ containing all two-element subsets of $[1,\mathrm{\ell }]$. We use the alphabet $\mathrm{\Sigma }=V\cup \{0,1\}\cup \{z_i\mid i\in [\mathrm{\ell }]\}$. We add the following jobs:

• $\mathrm{■}$

  for each $v\in V_i$, we add one job $J_v=(w_v,1)$ where $w_v$ starts with $x{z}_i$. Afterwards, for each $q\in [1,\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)]$, we append the following four letters:

  • –

    if $i\notin f(q)$, then we append $0000$,

  • –

    if $f(q)=\{i,i^{\prime }\}$ for some $i^{\prime }>i$, then we append $0v00$, and

  • –

    if $f(q)=\{i^{\prime },i\}$ for some , then we append $000v$.

• $\mathrm{■}$

  for each edge $e=\{u,v\}\in E$ with $u\in V_i$ and $v\in V_{i^{\prime }}$ for some , we add one job $J_e=(xu0v,4\cdot (f(\{i,i^{\prime }\})-1)+2)$.

The capacities are as follows:

• $\mathrm{■}$

  for each $i\in [1,\mathrm{\ell }]$, letter $z_i$ has capacity 1 at time 1 and capacity $|V_1|-1$ at time 2,

• $\mathrm{■}$

  for each $v\in V$, letter $v$ has capacity $r$ at every time step, and

• $\mathrm{■}$

  all other capacities are set to be $\mathrm{\infty }$.

Finally, we set $k:=\mathrm{\ell }+\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)$. Note that $T=4\cdot \left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)+2$. As the reduction can clearly be computed in polynomial time, it remains to show correctness.

Before we show the correctness, we provide some intuition. The capacities of $z_i$ at time 1 ensures that at most one deletion occurs in jobs $\{J_v\mid v\in V_i\}$, while the capacities of $z_i$ at time 2 ensure that at least one deletion occurs in $\{J_v\mid v\in V_i\}$. Therefore, exactly one deletion occurs in $\{J_v\mid v\in V_i\}$ for every $i\in [1,\mathrm{\ell }]$. These $\mathrm{\ell }$ vertices with a deletion correspond to a multicolored clique: Since there exists some unique $v_i\in V_i$ such that the $x$ in $J_{v_i}$ is deleted, this implies that all occurrences of $v_i$ in $J_{v_i}$ move one time step earlier. Thereby, for each $q\in [1,\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)]$ with $i\in f(q)$, letter $v_i$ from $J_{v_i}$ “collides” with letter $v_i$ in $J_e$ the $r$ edges $e$ incident to $v_i$ in $E[V_i,V_{i^{\prime }}]$ where $i^{\prime }=f(q)\setminus \{i\}$. Because the capacity of $v_i$ is $r$ at each time step, this implies that a deletion has to occur in $J_e$ for some edge $e\in E[V_i,V_{i^{\prime }}]$ incident to $v_i$. As the budget allows for $k-\mathrm{\ell }=\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)$further deletions, this implies that there is exactly one edge in $E[V_i,V_{i^{\prime }}]$ with a deletion for $\{i,i^{\prime }\}\in \left(\genfrac{}{}{0pt}{}{[1,\mathrm{\ell }]}{2}\right)$. Since this edge needs to be incident to both $v_i$ and $v_{i^{\prime }}$, it follows that $\{v_i\mid i\in [1,\mathrm{\ell }]\}$ is a multicolored clique.

We first show that if $G$ is a yes-instance to Multicolored Clique, then $(T,𝒥,c,k)$ is yes-instance of WTR. Given a clique $\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$ with $v_i\in V_i$, we construct a solution to the WTR instance as follows: We remove the unique occurrence of $x$ in job $J_{v_i}$ for each $i\in [1,\mathrm{\ell }]$ and in job $J_{\{v_{i_1},v_{i_2}\}}$ for . We call the resulting strings ${\tilde{w}}_v$ for $v\in V$ and ${\tilde{w}}_e$ for $e\in E$. As we removed $k$ occcurences of $x$ in total, it remains to show that the capacity constraints are satisfied. For letter $z_i$, we have a load of 1 at time 1 (from job $J_{v_i}$) and a load of $|V_1|-1$ at time to (from jobs $J_v$ for $V\in V_i\setminus \{v_i\}$). Thus, the capacities of $z_i$ are satisfied. For $v\in V\setminus \{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$, the maximum load at any time is $\mathrm{deg}(v)=r$, so its capacity is satisfied. We continue with letter $v_i$ for $i\in [1,\mathrm{\ell }]$. At time $4\cdot (q-1)+3$, the load of $v_i$ is either 0 (if $i\notin f(q)$ or $f(q)=\{i,i^{\prime }\}$ for some ) or $r$ (if $f(q)=\{i,i^{\prime }\}$ for some $i^{\prime }>i$; in this case, job $J_{v_i}$ and $r-1$ edge jobs (all edges from $E[V_i,V_{i^{\prime }}]\cap \delta (v_i)$ except for $\{v_i,v_{i^{\prime }}\}$). In both cases, the capacity constraint is satisfied. Symetrically, at time $4\cdot (q-1)+5$, the load is either 0 (if $i\notin f(q)$ or $f(q)=\{i,i^{\prime }\}$ for some $i^{\prime }>i$) or $r$ (if $f(q)=\{i,i^{\prime }\}$ for some ; in this case, job $J_{v_i}$ and $r-1$ edge jobs (all edges from $E[V_i,V_{i^{\prime }}]\cap \delta (v_i)$ except for $\{v_i,v_{i^{\prime }}\}$). In both cases, the capacity constraint is satisfied.