Sorting by Strip Swaps is NP-Hard
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915589254021120 |
|---|---|
| author | Roy, Swapnoneel Asaithambi, Asai Mukhopadhyay, Debajyoti |
| author_facet | Roy, Swapnoneel Asaithambi, Asai Mukhopadhyay, Debajyoti |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00015 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sorting by Strip Swaps is NP-Hard Roy, Swapnoneel Asaithambi, Asai Mukhopadhyay, Debajyoti Data Structures and Algorithms Artificial Intelligence Computational Complexity 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. |
| title | Sorting by Strip Swaps is NP-Hard |
| topic | Data Structures and Algorithms Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2511.00015 |