{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigrvswo2pd6gpankwyz5gzlufg4xn5vnjcj5ipvc5g6ptwek2f74y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mjw3xbtkklg2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.16030v1",
  "publishedAt": "2026-04-20T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sotiris Kanellopoulos",
    "Giorgos Mitropoulos",
    "Christos Pergaminelis",
    "Thanos Tolias"
  ],
  "textContent": "**Authors:** Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias\n\nThe 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., SODA 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 $\\sqrt{2}-1/2\\approx 0.9142$ lower bound for the density threshold of 2-Visits and prove that the density threshold of k-Visits approaches $5/6\\approx 0.8333$ for $k \\to \\infty$.",
  "title": "Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants"
}