Advancing the Transposition Distance and Diameter through Lonely Permutations

• Published in: SIAM journal on discrete mathematics 2013-01, Vol.27 (4), p.1682-1709
• Main Authors: Cunha, Luís Felipe I., Kowada, Luis Antonio B., de A. Hausen, Rodrigo, de Figueiredo, Celina M. H.
• Format: Article
• Language: English
• Subjects: Alternating current; Approximation; Genomes; Lower bounds; Mathematical analysis; Permutations; Sorting; Unions
• ISSN: 0895-4801; 1095-7146
• DOI: 10.1137/120899753

Sorting by transpositions is a challenging classic problem proposed in genome rearrangement and recently settled as NP-hard. Although the proven hard to sort $3$-permutations are close to the identity, the historical approach has been to study distant permutations, possible candidates to be diametral. The transposition diameter is a related challenging problem, known only for $n \leq 15$. We advance the study of both transposition distance and diameter by considering lonely permutations and the union operation. We present tighter bounds for the distance of lonely $3$-permutations, $u_{n,n-1}$, $u_{n,\frac{n}{2}}$, $u_{n,3}$, and $u_{n,4}$. We set the current lower bound for the transposition diameter back to $\big\lfloor\frac{n+1}{2}\big\rfloor+1$ and propose an alternative union of lonely permutations contributing to the approach used so far in the literature. [PUBLICATION ABSTRACT]