Generalized Sorting via Four-Cycles
We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as po...