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.

An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of G-v to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of k.

Genome rearrangement has been an active area of research in computational comparative genomics for the last three decades. While initially mostly an interesting algorithmic endeavor, now the practical application of rearrangement distance methods and more advanced phylogenetic tasks is becoming common practice, given the availability of many completely sequenced genomes. Several genome rearrangement models have been developed over time, sometimes with surprising computational properties. A prominent example is the fact that computing the reversal distance of two signed permutations is possible in linear time, while for two unsigned permutations it is NP-hard. Therefore one has to always be careful about the precise problem formulation and complexity analysis of rearrangement problems in order not to be fooled. The double distance is the minimum number of genomic rearrangements between a singular and a duplicated genome that - in addition to rearrangements - are separated by a whole genome duplication. At the same time it allows to assign the genes of the duplicated genome to the two paralogous chromosome copies that existed right after the duplication event. Computing the double distance is another example of a tricky hardness landscape: If the distance measure underlying the double distance is the simple breakpoint distance, the problem can be solved in linear time, while with the more elaborate DCJ distance it is NP-hard. Indeed, there is a whole family of distance measures, parameterized by an even number $k$, between the breakpoint distance ($k=2$) at the one end and the DCJ distance ($k=\infty$) at the other end. Only little was known about the hardness border that lies somewhere on the way between these two extremes. Precisely, beneath the two border cases the (linear) problem complexity was known only for $k=4$ and $k=6$. In this paper we close the gap, giving a full picture of the hardness landscape when computing the double distance.

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

Summary The ‐admissibility is a min‐max problem that concerns to determine whether a graph contains a spanning tree in which the distance between any two adjacent vertices of is at most in . The stretch index of , , is the smallest for which is ‐admissible. This problem is in P for , NP‐complete for , , and remaining open for . In a very recent development, Couto et al. (Inf Process Lett, 2022;177: 106265) introduced both sequential and parallel algorithms for constructing spanning trees. Additionally, they proposed two greedy heuristics for generating a candidate solution tree, but they left unresolved the issue of how to decide between two vertices when both have equal chances of being chosen in a greedy step. This criterion is important, since different branches can yield different stretch indexes. In response to this question, we developed nine new heuristics that use the concept of vertex importance in complex networks. Our research evaluates results on several types of graphs, including Barabási‐Albert, Erdős‐Rényi, Watts‐Strogatz, and bipartite graphs. Furthermore, we introduce a new parallel algorithm that employs a method using induced cycle of the graph to compare its performance with previously proposed algorithms. We develop a deep analysis on the proposed strategies (parallel and heuristics) comparing all of them to the other ones in the literature and as a result we obtain the best results so far in order to obtain exact values (or heuristics) of stretch indexes.

Important papers have appeared recently on the problem of indexing binary strings for jumbled pattern matching, and further lowering the time bounds in terms of the input size would now be a breakthrough with broad implications. We can still make progress on the problem, however, by considering other natural parameters. Badkobeh et al. (IPL, 2013) and Amir et al. (TCS, 2016) gave algorithms that index a binary string in O(n + r^2 log r) time, where n is the length and r is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in O(n + r^2) time. In this paper we propose a new and very simple algorithm that also runs in O(n + r^2) time and can be extended either so that the index returns the position of a match (if there is one), or so that the algorithm uses only O(n) bits of space instead of O(n) words.

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.