Sorting by Strip Swaps is NP-Hard

2025/10/20 by Swapnoneel Roy, Roy, Swapnoneel, Asai Asaithambi +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms

paper · pdf · doi:10.48550/arxiv.2511.00015

openalex publication_date 2025/10/20 · openalex created_date 2025/11/05 · openalex updated_date 2026/07/28

Abstract

We show that Sorting by Strip Swaps (SbSS) is NP-hard by a polynomial reduction of Block Sorting. The key idea is a local gadget, a 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 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.

Related

• On Approximability of Block Sorting
• On Sorting by Bounded Block Interchanges
• Restricted Patience Sorting and Barred Pattern Avoidance
• Smoothed Complexity of SWAP in Local Graph Partitioning
• Sorting a Permutation by block moves