Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
This solves a long-standing open problem in sorting theory by providing optimal preprocessing and sorting times for directed acyclic graphs.
The paper achieves tight bounds for sorting under partial information: O(m) preprocessing time and O(log e(G)) sorting time, improving on previous O(n^ω) and O(log e(G) + m) results.
In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in $O(\log e(G))$ time, where $e(G)$ is the number of sorted orders compatible with $G$. Cardinal, Fiorini, Joret, Jungers and Munro [STOC'10] show that you can preprocess $G$ in $O(n^{2.5})$ time and then sort $X$ in $O(\log e(G) + n)$ time and $O(\log e(G))$ comparisons. Recent work of van der Hoog and Rutschmann [FOCS'24] implies an algorithm with $O(n^ω)$ preprocessing time where $ω< 2.372$ and $O(\log e(G))$ sorting time. Haeupler, Hladík, Iacono, Rozhoň, Tarjan and Tětek [SODA'25] achieve an overall running time of $O(\log e(G) + m)$. In this paper, we achieve tight bounds for this problem: $O(m)$ preprocessing time and $O(\log e(G))$ sorting time. As a key ingredient, we design a new fast heap data structure that might be of independent theoretical interest.