Dense Pinwheel Packing Is Strongly NP-Complete

Abstract

An instance of {\sc Pinwheel Packing} is a list of positive integers $a_1,\dots ,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 }_{i}1/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)$.