Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems

The (packing version of) Pinwheel Scheduling problem was introduced by Holte et al. [12] in 1989 as a formalization of a real-time scheduling problem. In the problem, we are given $k$ recurring tasks and a positive integer $a_i$ for each task $i\in [k]=\{1,\mathrm{\dots },k\}$. The objective is to select one task to perform each day so that each task $i$ is performed at least once every $a_i$ days. In other words, we want to find pairwise disjoint sets $S_1,\mathrm{\dots },S_k\subseteq \mathbb{Z}$ such that

for all $i\in [k]$ and $m\in \mathbb{Z}$, where $S_i$ represents the set of days on which task $i$ is performed. Note that each $S_i$ can be an infinite set. A natural computational problem is to determine the existence of such sets $S_1,\mathrm{\dots },S_k\subseteq \mathbb{Z}$, which is formally described as follows. Note that we call this problem Pinwheel Packing in this paper, because we will discuss the corresponding covering variant later.

Despite the simplicity and naturalness of the problem setting, little is known about the computational complexity of this problem. It has been shown in [12, Corollary 2.2] that Pinwheel Packing is in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$; however, it is unknown whether this problem is in $\mathrm{𝖭𝖯}$. Furthermore, it is unknown whether this problem is $\mathrm{𝖭𝖯}$-hard. See [19] for details.

Since each task $i$ has to be performed on at least a $\frac{1}{a_i}$ fraction of a sufficiently long consecutive sequence of days, if $A={(a_i)}_{i\in [k]}$ is a yes-instance of Pinwheel Packing, then ${\sum }_{i=1}^k\frac{1}{a_i}$ (called the density of $A$) is at most $1$. An instance $A={(a_i)}_{i\in [k]}$ is called dense if its density is exactly $1$. As we see in Section 1.2, for dense instances, Pinwheel Packing is equivalent to several other problems, highlighting that dense instances form an interesting special case. However, the exact complexity of dense instances of Pinwheel Packing has been open for more than 30 years. In fact, it is noted in [12, Section 4] that the $\mathrm{𝖭𝖯}$-hardness of this problem remains an open question, and it is explicitly conjectured by Kawamura and Soejima [21, Conjecture 19] that Pinwheel Packing for dense instances is $\mathrm{𝖭𝖯}$-complete. Note that the $\mathrm{𝖭𝖯}$-hardness has been shown when the input sequence is represented in a concise notation; see [12, Theorem 4.12] and [19, Theorem 5]. Jacobs and Longo showed in their preprint [16] that (dense instances of) Pinwheel Packing cannot be solved in polynomial time unless $\mathrm{𝖲𝖠𝖳}$ with $n$ variables has a randomized algorithm running in expected time $n^{O(\log n\log \log n)}$.

As mentioned in the previous subsection, for dense instances, Pinwheel Packing is equivalent to several other problems.

Observe that, if $S_1,\mathrm{\dots }{S}_k\subseteq \mathbb{Z}$ form a solution for a dense instance $A={(a_i)}_{i\in [k]}$ of Pinwheel Packing, then they satisfy (1) with equality. Using this observation, for dense instances, Pinwheel Packing is equivalent to the following exact variant.

Note that the desired condition of this problem means that each task $i$ is performed exactly once every $a_i$ days. Therefore, $S_i$ satisfies $\left|[m,m+a_i)\cap S_i\right|=1$ for all $m\in \mathbb{Z}$ if and only if it is a residue class modulo $a_i$, i.e., $S_i=\{r_i+a_i\cdot q:q\in \mathbb{Z}\}$ for some integer $r_i$. Independently of its connection to Pinwheel Packing, Exact Pinwheel Packing is an interesting problem in its own right. Indeed, Exact Pinwheel Packing has been studied under the name ($1$-server) periodic maintenance problem [3, 25, 30] in the context of scheduling problems, and its solution has also garnered attention in discrete mathematics under the name disjoint residue classes [15, 21, 28]. It is shown in [3, 16, 21, 25] that Exact Pinwheel Packing is $\mathrm{𝖭𝖯}$-complete, where we note that the input is not necessarily dense.

We can also consider a problem that is, in a sense, dual to (Exact) Pinwheel Packing, which is called (Exact) Pinwheel Covering [19]. Consider a scenario where a single task must be performed every day, and it is to be handled by $k$ agents. Each agent $i\in [k]$ is assigned a positive integer $a_i$, which represents the condition that the agent can perform the task at most once (or exactly once) every $a_i$ days. In this setting, the problem of determining the assignment of agents corresponds to finding a collection of sets $S_1,\mathrm{\dots },S_k\subseteq \mathbb{Z}$ such that ${\bigcup }_{i\in [k]}{S}_i=\mathbb{Z}$ and

for all $i\in [k]$ and $m\in \mathbb{Z}$, where $S_i$ represents the set of days on which agent $i$ performs the task. That is, the problem is formally described as follows.

Pinwheel Covering was introduced and studied under the name point patrolling in [21]. Similarly to the packing problem, this problem is in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$, and it is unknown whether this problem is $\mathrm{𝖭𝖯}$-hard. In contrast, very recently, it was shown that Exact Pinwheel Covering is $\mathrm{𝖭𝖯}$-hard [20]. Note that feasible solutions for Exact Pinwheel Covering are known as Erdős covering systems and have been actively studied by number theorists; see [2, 14].

Since each agent $i$ can perform a task on at most a $\frac{1}{a_i}$ fraction of a sufficiently long consecutive sequence of days, if $A={(a_i)}_{i\in [k]}$ is a yes-instance of Pinwheel Covering, then its density ${\sum }_{i=1}^k\frac{1}{a_i}$ is at least $1$. Similarly to the packing problem, if the density is exactly $1$, then Pinwheel Covering and Exact Pinwheel Covering are equivalent. Furthermore, if the density of $A={(a_i)}_{i\in [k]}$ is exactly $1$ and $S_1,\mathrm{\dots },S_k\subseteq \mathbb{Z}$ satisfy $\left|[m,m+a_i)\cap S_i\right|=1$ for all $i\in [k]$ and $m\in \mathbb{Z}$, then we see that ${\bigcup }_{i\in [k]}{S}_i=\mathbb{Z}$ if and only if $S_1,\mathrm{\dots },S_k$ are pairwise disjoint. By combining these facts, we arrive at the following observation.

For brevity, Pinwheel Packing, when restricted to dense instances, is referred to as Dense Pinwheel Packing. Then, Observation 1 implies that Dense Pinwheel Packing is a special case of all the four above problems.

As described in Section 1.1, it was shown by Jacobs and Longo [16] that Dense Pinwheel Packing cannot be solved in polynomial time unless $\mathrm{𝖲𝖠𝖳}$ with $n$ variables has a randomized algorithm running in expected time $n^{O(\log n\log \log n)}$. The first contribution of this paper is to strengthen this result by showing that Dense Pinwheel Packing cannot be solved in polynomial time under a weaker complexity assumption, partially addressing the open question in [12, Section 4] and [21, Conjecture 19].

Here, $\mathrm{𝖭𝖯}\subseteq \mathrm{𝖣𝖳𝖨𝖬𝖤}(n^{O(\log n)})$ means that every problem in $\mathrm{𝖭𝖯}$ can be solved in $n^{O(\log n)}$ time, where $n$ is the input size of the problem. The assumption $\mathrm{𝖭𝖯}⊈\mathrm{𝖣𝖳𝖨𝖬𝖤}(n^{O(\log n)})$ is weaker than the assumption in [16] in two key aspects: the running time is improved from $n^{O(\log n\log \log n)}$ to $n^{O(\log n)}$, and our assumption does not rely on randomization. Note that the assumption $\mathrm{𝖭𝖯}⊈\mathrm{𝖣𝖳𝖨𝖬𝖤}(n^{O(\log n)})$ is weaker than the Exponential Time Hypothesis (ETH) and $\mathrm{𝖭𝖯}⊈\mathrm{𝖰𝖯}$ (see Corollary 10), while it is stronger than $𝖯\ne \mathrm{𝖭𝖯}$. Theorem 2 implies that Pinwheel Packing and Pinwheel Covering cannot be solved in polynomial time under the same assumption.

In our proof for Theorem 2, we refine the argument in [16]. We first prove that Exact Pinwheel Packing is hard even when $\mathrm{lcm}(A)$ is not particularly large (see Theorem 6), where $\mathrm{lcm}(A)$ denotes the least common multiple of $a_1,\mathrm{\dots },a_k$ for $A={(a_i)}_{i\in [k]}$. We then reduce Exact Pinwheel Packing to Dense Pinwheel Packing by appending multiple copies of integer $\mathrm{lcm}(A)$, thereby proving the hardness of Dense Pinwheel Packing. The primary technical challenge lies in ensuring that $\mathrm{lcm}(A)$ does not become excessively large.

To achieve this, Jacobs and Longo [16] reduce an $\mathrm{𝖭𝖯}$-hard problem of size $n$ to a new problem called Partial Coding, and then further reduce it to Exact Pinwheel Packing. These reductions show that Exact Pinwheel Packing is hard even when $\mathrm{lcm}(A)=n^{O(\log n\log \log n)}$. In contrast, we directly and carefully reduce an $\mathrm{𝖭𝖯}$-hard problem to Exact Pinwheel Packing, which enables us to achieve a tighter bound of $\mathrm{lcm}(A)=n^{O(\log n)}$. To derandomize our reduction step, we utilize a sophisticated tool known as $(n,k)$-universal sets [26] in a non-trivial manner, which constitutes the most technical aspect of our proof. For details, see Section 2.

Theorem 2 suggests that (Exact) Pinwheel Packing and (Exact) Pinwheel Covering are unlikely to be solvable in polynomial time. It is then natural to consider the fixed-parameter tractability of these problems. Indeed, Gąsieniec et al. [10] showed that Pinwheel Packing can be solved in FPT time when parameterized by $k$. Our second contribution is to show that the remaining three variants can also be solved in FPT time with respect to the parameter $k$.

We here describe proof ideas for these theorems, while formal proofs are given in Section 3. Our proof for Theorem 4 is based on the following intuition: if some $a_i$ is extremely large, then removing $a_i$ does not affect the feasibility of the problems. Our technical contribution lies in formalizing this intuition. We then show that it is sufficient to consider the case where each $a_i$ is bounded by a function of $k$, leading to FPT algorithms.

It should be noted that this argument does not apply to Exact Pinwheel Packing, as removing a large $a_i$ could affect the feasibility of the problem. For instance, if $A$ consists of two large integers $a_1$ and $a_2$ that are coprime, then $A$ is a no-instance. However, removing either $a_1$ or $a_2$ would result in a yes-instance. Therefore, we adopt a completely different approach to obtain Theorem 5. We observe that a solution to Exact Pinwheel Packing consists of sets $S_i=\{r_i+a_i\cdot q:q\in \mathbb{Z}\}$, where each set is determined by an integer $r_i$. Treating $r_1,\mathrm{\dots },r_k$ as integer variables, we show that the constraints for $r_i$ can be formulated as an integer linear program by introducing several auxiliary variables. Since the integer linear programming problem can be solved in FPT time, parameterized by the number of variables, this yields an FPT algorithm for Exact Pinwheel Packing.

Moreover, to highlight the similarities and differences between Pinwheel Packing and (Exact) Pinwheel Covering, an FPT algorithm for Pinwheel Packing with an explicit running time bound is provided in Appendix A.

A generalization of Pinwheel Packing has been studied under the name of Windows Scheduling Problem. While Pinwheel Packing can be viewed as a scheduling problem involving a single machine where all tasks have the same size, Windows Scheduling Problem extends this to a setting with multiple machines and tasks of varying sizes [4, 5, 16, 22].

Bamboo Garden Trimming problem is an optimization variant of Pinwheel Packing. Here, the objective is to find the smallest positive number $h$ such that ${(h\cdot a_i)}_{i\in [k]}$ is a yes-instance of Pinwheel Packing. Hardness results and approximation algorithms have been investigated for this problem [9, 11, 29].

For Pinwheel Packing, there has been extensive research on sufficient conditions for the density of the input $A$ to be a yes-instance. It is not so difficult to show that $A$ is a yes-instance if its density is at most $\frac{1}{2}$ [12]. A central question in this area is whether the same statement holds when $\frac{1}{2}$ is replaced with a larger number $\alpha$. The maximum such number $\alpha$ is called the density threshold. Since $A=(2,3,m)$ is a no-instance with a density of $\frac{5}{6}+\frac{1}{m}$ for any integer $m$, the density threshold is at most $\frac{5}{6}$. Building on extensive research on the density threshold [6, 7, 10, 24], Kawamura [18] recently showed that the density threshold is exactly $\frac{5}{6}$, resolving the conjecture proposed by Chan and Chin [6]. A threshold depending on the smallest element in $A$ is investigated in [11]. It is also shown that if $A$ consists of at most two distinct values and its density is at most $1$, then it is a yes-instance [13].

In this subsection, we prove the hardness of Dense Pinwheel Packing using Theorem 6.

In this subsection, we give a proof of Lemma 7. Let $G=(V,E)$ be a graph with $|V|=n$ whose maximum degree is four. A vertex subset $I\subseteq V$ is called an independent set if no two vertices in $I$ are adjacent to each other. Our idea is to find a family $ℐ$ of independent sets in $G$ such that

(I)

for any pair of non-adjacent vertices $v,v^{\prime }\in V$, there exists $I\in ℐ$ such that $\{v,v^{\prime }\}\subseteq I$.

In this subsection, we deal with Pinwheel Covering and Exact Pinwheel Covering simultaneously and prove Theorem 4. We first present the following claim. Although this claim was already shown in [21, Section 4.1] for Pinwheel Covering, we here give a proof for completeness.

In this subsection, we deal with Exact Pinwheel Packing and prove Theorem 5.