{"ID":2852853,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00015","arxiv_id":"2511.00015","title":"Sorting by Strip Swaps is NP-Hard","abstract":"We show that \\emph{Sorting by Strip Swaps} (SbSS) is NP-hard by a polynomial reduction of \\emph{Block Sorting}. The key idea is a local gadget, a \\emph{cage}, that replaces every decreasing adjacency $(a_i,a_{i+1})$ by a guarded triple $a_i,m_i,a_{i+1}$ enclosed by guards $L_i,U_i$, so the only decreasing adjacencies are the two inside the cage. Small \\emph{hinge} gadgets couple adjacent cages that share an element and enforce that a strip swap that removes exactly two adjacencies corresponds bijectively to a block move that removes exactly one decreasing adjacency in the source permutation. This yields a clean equivalence between exact SbSS schedules and perfect block schedules, establishing NP-hardness.","short_abstract":"We show that \\emph{Sorting by Strip Swaps} (SbSS) is NP-hard by a polynomial reduction of \\emph{Block Sorting}. The key idea is a local gadget, a \\emph{cage}, that replaces every decreasing adjacency $(a_i,a_{i+1})$ by a guarded triple $a_i,m_i,a_{i+1}$ enclosed by guards $L_i,U_i$, so the only decreasing adjacencies a...","url_abs":"https://arxiv.org/abs/2511.00015","url_pdf":"https://arxiv.org/pdf/2511.00015v1","authors":"[\"Swapnoneel Roy\",\"Asai Asaithambi\",\"Debajyoti Mukhopadhyay\"]","published":"2025-10-20T15:51:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\",\"cs.CC\"]","methods":"[]","has_code":false}