Sorting and selection in posets

ABSTRACT

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks.

Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n(w + log n)). We also describe a variant of Mergesort with query complexity O(wn log n/w) and total complexity O(w²n log n/w); an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations.

We also consider two related problems: finding the minimal elements, and its generalization to 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. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

REFERENCES

• 1: P. Boldi and F. Chierichetti and S. Vigna. "Pictures from Mongolia --- Partial Sorting in a Partial World," FUN 2007.
• 2: Graham Brightwell, Balanced pairs in partial orders, Discrete Mathematics, v.201 n.1-3, p.25-52, April 28, 1999 [doi>10.1016/S0012-365X(98)00311-2]
• 3: G. Brightwell and S. Goodall. "The Number of Partial Orders of Fixed Width," Order 20(4): 333--345, 2003.
• 4: Graham Brightwell , Peter Winkler, Counting linear extensions is #P-complete, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.175-181, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103441]
• 5: Y. Chen. "Decomposing DAGs into Disjoint Chains," Database and Expert Systems Applications 2007.
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: C. Daskalakis, R. M. Karp, E. Mossel, S. Riesenfeld, E. Verbin. "Sorting and Selection in Posets," ArXiv Report, 2007.
• 8: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 9: U. Faigle , G. Turán, Sorting and recognition problems for ordered sets, SIAM Journal on Computing, v.17 n.1, p.100-113, Feb. 1988 [doi>10.1137/0217007]
• 10: L. R., Jr., Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• 11: M. Fredman. "How good is the information theory bound in sorting?" Theor. Comput. Sci. 1(4): 355--361, 1976.
• 12: Frank Fussenegger , Harold N. Gabow, A Counting Approach to Lower Bounds for Selection Problems, Journal of the ACM (JACM), v.26 n.2, p.227-238, April 1979 [doi>10.1145/322123.322128]
• 13: Jeff Kahn , Jeong Han Kim, Entropy and sorting, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.178-187, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129731]
• 14: J. Kahn and M. Saks. "Balancing poset extensions," Order 1(2): 113--126, 1984.
• 15: S. S. Kislitsyn, "A finite partially ordered set and its corresponding set of permutations," Matematicheskie Zametki 4(5): 511--518, 1968.
• 16: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 17: N. Linial. "The Information theoretic bound is good for merging," SIAM J. Comput. 13(4): 795--801, 1984.
• 18: M. E. J. Newman, SIAM Review 45: 167--256, 2003.
• 19: Krzysztof Onak , Pawel Parys, Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.379-388, October 21-24, 2006 [doi>10.1109/FOCS.2006.32]
• 20: W. Trotter and S. Felsner, "Balancing pairs in partially ordered sets," Combinatorics, Paul Erdos is Eighty I: 145--157, 1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms