Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs of objects are incomparable. This generalization is relevant in applications related to rankings in sports, college admissions, or conference submissions. It also has potential applications in biology, such as comparing the evolutionary fitness of different strains of bacteria, or understanding input-output relations among a set of metabolic reactions or the causal influences among a set of interacting genes or proteins. Our results improve and extend results from two decades ago of Faigle and Turán, who were the first to consider some of the problems considered here. A poset is defined as a set of elements with a transitive partial order where some pairs of elements may be incomparable. A measure of complexity of a poset is given by its width, which is the maximum size of a set of mutually incomparable elements. We consider algorithms that obtain information about a poset by queries that compare two elements. We consider two complexity measures: query complexity, which counts only the number of queries, and total complexity, which counts all operations. We present an algorithm that sorts a width w poset of size n and has query complexity O(n(w + log n)), which is within a constant factor of the information-theoretic lower bound. We also show that a variant of Mergesort has query complexity O(wn log n w ) and total complexity O(w 2 n log n w ). Faigle and Turán have shown that the sorting problem has query complexity O wn log n w but did not address the total compexity of the problem. Two problems related to sorting are the problem of finding the minimal elements in a poset and its generalization of finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(wn) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. We also derive upper bounds on the total complexity of some other problems of a similar flavor, such as computing a linear extension of a poset and computing the heights of all elements. Many open problems remain, of which the most significant is to determine the precise total complexity of sorting, as well as the precise query and total complexity of k-selection. It would also be interesting to find efficient static and dynamic data structures that play the same role for partial orders that heaps and binary search trees play for total orders.
A poset is defined as a set of elements with a transitive partial order, where some elements may be incomparable REF .
Sorting and Selection in Posets
ArXiv
ArXiv
Mathematics Computer Science