HEXAGONbeta

Set Cover by Cyclic Rotations Is NP-Complete

Primarily AI-generated textHuman understanding: no partscs.CC — Computational Complexity

Contributed by YURAN XIU ↗

Version 1 / Oct 17, 2026 / CC BY 4.0

Abstract

Given an explicitly listed binary pattern of positive length nn and a nonnegative integer bb in binary, can at most bb cyclic rotations of the pattern cover all nn positions? We prove that this decision problem is NP-complete. The reduction constructs a pattern in a cyclic group of polynomial order and outputs its entire indicator word. Its principal ingredient is a replicated-marker construction: a cover within the budget must choose one translate in every layer, and each failed difference constraint leaves a block of more holes than the remaining translates can cover. Combining this construction with the known embedding of graph cliques into circulant graphs using distinct three-term sums gives a polynomial-time reduction from 33SAT. The theorem allows every subset, including the empty pattern, and every binary budget. A Lean formalization checks the mathematical reduction, the full-word polynomial-time programs, NP membership, and the unconditional NP-hardness foundation. HAL deposit: hal-05800233v1.

References

  1. Open Problems from WADS 2023 . Problem 4: Set-Cover by Rotations, contributed by Anthony Wirth, 2023. https://wadscccg2023.encs.concordia.ca/assets/pdf/wads_open_problems.pdf.link
  2. Anthony Ian Wirth. Approximation Algorithms for Clustering . Ph.D. dissertation, Princeton University, January 2005. Section 2.7, ``Pattern rotation,'' pp. 34--37. https://www.cs.princeton.edu/techreports/2004/716.pdf.link
  3. Béla Bollobás, Svante Janson, and Oliver Riordan. On covering by translates of a set . arXiv:0910.3815v2, 2010. https://arxiv.org/abs/0910.3815v2.arXiv
  4. Bruno Codenotti, Ivan Gerace, and Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra and its Applications , 285(1--3):123--142, 1998.
  5. Chris Godsil and Brendan Rooney. Hardness of Computing Clique Number and Chromatic Number For Cayley Graphs . arXiv:1502.00965v5, 2016. Section 6, especially Lemma 6.1. https://arxiv.org/abs/1502.00965v5.arXiv
  6. The complexitylib contributors. Complexitylib: a Lean 4 formalization of computational complexity theory . Source revision add0aca8ee0d71e68969f2cb45cf91554a50f787 . https://github.com/SamuelSchlesinger/complexitylib/tree/add0aca8ee0d71e68969f2cb45cf91554a50f787.link

Version history

  1. v1Submitted by YURAN XIUInitial depositCurrentOct 17, 2026