Dense pinwheel packing scheduling problem is strongly NP-complete
Dense Pinwheel Packing Is Strongly NP-Complete
Computational Complexity
Summary
The paper studies a scheduling problem where tasks must be arranged so each one appears frequently within certain intervals. When the schedule is dense, meaning the total frequencies fill all time slots exactly, the problem turns out to be very hard to solve quickly. The authors prove that even when task frequencies are written out in full and tasks with the same frequency are counted separately, deciding if such a schedule exists is strongly NP-complete. This means no fast algorithm is expected for this problem, even under stricter input conditions.
What this means in practice
- •For real-time system designers: Avoid expecting efficient algorithms for densely packed periodic scheduling tasks when exact task frequency constraints apply.
- •For compiler engineers: Recognize inherent complexity limits in scheduling tasks evenly with strict repetition constraints, guiding heuristic or approximate scheduling techniques.
A theory result. No direct application yet.
Authors
Yusuke Kobayashi, Bingkai Lin, Joseph Swernofsky
Abstract
An instance of {\sc Pinwheel Packing} is a list of positive integers $a_1,\ldots,a_k$. A feasible schedule assigns one task to every integer time so that every interval of $a_i$ consecutive times contains task $i$. The instance is \emph{dense} when $\sum_i1/a_i=1$. We prove that {\sc Dense Pinwheel Packing} is NP-complete even when every period is encoded in unary and equal periods are listed as distinct tasks. Consequently, the usual binary-encoded problem is strongly NP-complete. Kleinberg and Mishra also prove NP-completeness \cite[Corollary~5.1]{KleinbergMishra2026}, but their reduction uses periods of exponential numerical size and therefore yields only weak NP-hardness. Our proof uses a direct reduction from triangle partition in a sparse tripartite graph. If each of the three parts of the source graph has $n$ vertices, the reduction produces $O(n^4\log^3 n)$ explicitly listed tasks, each with period $O(n^4\log^3 n)$; consequently, its full unary encoding has length $O(n^8\log^6 n)$.