2026-08-27T21:20:08Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27523 2026-08-27T06:04:07Z ddc:004 open_access
On the Complexity of the (𝓁, k)-Median Problems Cunha, LuΓ­s Nascimento, Thiago Braga, Marilia D. V. Stoye, Jens Genome rearrangement median problem sigma-k distance The genome median problem is a central computational problem in comparative genomics, as it models the reconstruction of an ancestral genome from a set of related genomes. Given 𝓁 genomes and a distance measure, the problem asks for a genome that minimizes the sum of the distances to the input genomes. Two classical distances are the breakpoint distance and the double-cut-and-join (DCJ) distance. For multichromosomal circular genomes, the median problem is polynomial-time solvable under the breakpoint distance, whereas it is NP-hard under the DCJ distance. For even integer k β‰₯ 2, the Οƒ_k distance interpolates between these two extremes: Οƒβ‚‚ corresponds to the breakpoint distance, while Οƒ_∞ corresponds to the DCJ distance. A central open problem in this setting is the (3,4)-Median problem, which asks for a median of three genomes under the Οƒβ‚„ distance, the first intermediate distance after the breakpoint distance. Motivated by this question, we study the more general (𝓁,k)-Median problem, in which 𝓁 is the number of input genomes and k determines the Οƒ_k distance. We prove that (𝓁,6)-Median for every 𝓁 β‰₯ 4 and (3,12)-Median are NP-complete. We then extend the hardness of (𝓁,6)-Median to (𝓁,k)-Median for all even k β‰₯ 6, and the hardness of (3,12)-Median to (3,k)-Median for all even k β‰₯ 12. These results identify broad hardness regions in the (𝓁,k) parameter space and delimit the remaining open cases around the fundamental (3,4)-Median problem. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik LuΓ­s Cunha and Thiago Nascimento and Marilia D. V. Braga and Jens Stoye 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.19 urn:nbn:de:0030-drops-275231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode