2024/09/15 by Luís Cunha, Cunha, Luís, Thiago Lopes +3 · 1 citation
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · #68R05 #Chromosomal and Genetic Variations #Computational Complexity (cs.CC) #FOS: Computer and information sciences #G.2.0 #Genome Rearrangement Algorithms #Phytase and its Applications #acm:68R05 #cs.CC #msc:68R05
paper · pdf · doi:10.48550/arxiv.2409.09734
openalex publication_date 2024/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28 · arxiv created 2026/07/29 · arxiv updated 2026/07/31
Genome rearrangement distances provide a combinatorial framework for comparing genomes represented as permutations. Although the swap distance between two permutations is polynomial-time computable, optimization over multiple permutations is harder. Given three inputs, Swap Median minimizes the sum of distances to them, while Swap Closest minimizes the maximum distance. We prove that the decision version of Swap Median is NP-complete for three permutations, resolving a question open since Eriksen (2007). The reduction considers instances in which a solution exists exactly when the triangle-inequality lower bound is attained. We represent pairs of cycle decompositions by a graph whose vertices correspond to swaps that simultaneously break cycles and whose edges encode incompatible swaps. This graph class contains all 2-subdivision graphs; the hardness of Maximum Independent Set on this class then implies NP-completeness. We extend the construction to show that Swap Closest is also NP-complete for three inputs, strengthening Popov's result for an arbitrary number of permutations. Finally, the same graph-theoretic framework yields approximation procedures: selecting compatible cycle-breaking swaps improves the standard 4/3 metric bound for Swap Median and the standard 2 metric bound for Swap Closest by explicit terms relative to the median lower bound and input diameter, respectively.