2024/07/31 by Ivor van der Hoog, van der Hoog, Ivor, Eva Rotenberg +3 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2407.21591
openalex publication_date 2024/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Fredman proposed in 1976 the following algorithmic problem: Given are a ground set X, some partial order P over X, and some comparison oracle OL that specifies a linear order L over X that extends P. A query to OL has as input distinct x, x' ∈ X and outputs whether x <L x' or vice versa. If we denote by e(P) the number of linear extensions of P, then log e(P) is a worst-case lower bound on the number of queries needed to output the sorted order of X. Fredman did not specify in what form the partial order is given. Haeupler, Hladík, Iacono, Rozhon, Tarjan, and Tětek ('24) propose to assume as input a directed acyclic graph, G, with m edges and n=|X| vertices. Denote by PG the partial order induced by G. Algorithmic performance is measured in running time and the number of queries used, where they use Θ(m + n + log e(PG)) time and Θ(log e(PG)) queries to output X in its sorted order. Their algorithm is worst-case optimal in terms of running time and queries, both. Their algorithm combines topological sorting with heapsort. Their analysis relies upon sophisticated counting arguments using entropy, recursively defined sets defined over the run of their algorithm, and vertices in the graph that they identify as bottlenecks for sorting. In this paper, we do away with sophistication. We show that when the input is a directed acyclic graph then the problem admits a simple solution using Θ(m + n + log e(PG)) time and Θ(log e(PG)) queries. Especially our proofs are much simpler as we avoid the usage of advanced charging arguments and data structures, and instead rely upon two brief observations.