Simpler Optimal Sorting from a Directed Acyclic Graph.

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 orders that extend P, then it follows from basic information theory that 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. Their 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, both in terms of running time and queries. 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.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 instead rely upon two observations.