2026-09-08T01:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26511 2026-09-05T19:46:10Z ddc:004 open_access

Hardness, Tractability and Density Thresholds of Finite Pinwheel Scheduling Variants Kanellopoulos, Sotiris Mitropoulos, Giorgos Pergaminelis, Christos Tolias, Thanos Pinwheel Scheduling Perpetual Scheduling NP-Completeness Parameterized Complexity The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether there exists a schedule of length kn executing each task exactly k times, with no deadline expiring between consecutive visits (executions) of each task. In this work we prove that 2-Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2, settling an open question from [Kanellopoulos et al., 2026] and contrasting the tractability of 2-Visits for simple sets. On the other hand, we prove that 2-Visits is in RP when the number of distinct deadlines is constant, thus making progress on another open question regarding the parameterization of 2-Visits by the number of numbers. We then generalize all existing positive results for 2-Visits to a version of the problem where some tasks must be visited once and some other tasks twice, while providing evidence that some of these results are unlikely to transfer to 3-Visits. Lastly, we establish bounds for the density thresholds of k-Visits, analogous to the (5/6)-threshold of Pinwheel Scheduling [Kawamura, STOC 2024]; in particular, we show a √2-1/2≈ 0.9142 lower bound for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches 5/6≈ 0.8333 for k → ∞. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sotiris Kanellopoulos and Giorgos Mitropoulos and Christos Pergaminelis and Thanos Tolias 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.122 urn:nbn:de:0030-drops-265115 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.122 eng https://creativecommons.org/licenses/by/4.0/legalcode