You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons c[0], ..., c[k] for those items (e.g. c[0] = (x[0] < x[4]), c[1] = (x[3] > x[7]), etc.).
The objective is to sort the items by requesting as few additional comparisons as possible.
For example, if c contains all the pairwise comparisons, then you don't need to request any additional ones to be able to sort the list. If c contained nothing, then you'd request O(n*log(n)) additional comparisons to perhaps quicksort the items. But if c contained something in between, how could we smartly leverage those existing comparisons to guide the extra comparisons we request?
Computation time doesn't matter (so long as it's sub-exponential). All that matters is the algorithm requests roughly the fewest additional comparisons.
Vaguely, I have an idea about constructing a DAG from the comparisons in c, and then doing a topological sort for the DAG to get a partial ordering, but I'm not sure where to go from there.
