Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps

Abstract

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^{\ddot{I}}‰)$ preprocessing time where $\ddot{I}‰<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.

Submitted to FOCS