Sorting and Selection Problems in Partially Ordered Sets

In this thesis we present some results from the literature regarding sorting and selec­ tion problems in partially ordered sets. In the sorting problem we are given a partially ordered set U and access to an oracle function c : U × U → {≼, ≻, ̸∼}. We are able to compare two elements of U , only by querying the oracle function. Our goal is to retrieve the underlying unknown partial order. In the k­selection problem, we are required to find the k­smallest elements in the same setting. In particular we examine two models, the Width­Based Model [1] and the Forbidden Comparisons Model [2]. In the Width­ Based Model we are additionally given an upper bound w on the width of the underlying poset. The main result we present in this setting is the query­optimal Entropy Sort algo­ rithm with O(n log n+nw) query complexity, but exponential overall time [1]. We also examine some randomised and deterministic algorithms in this setting for the selection problem. On the other hand, the Forbidden Comparisons Model, the oracle function is defined slightly differently, i.e. c : U × U → {≼, ≻, ⊥}, where c(a, b) =⊥ when we are not allowed to compare the two elements a, b; we deduce their relation (if possible) through transitivity. We are also given an undirected comparison graph G = (V, E), where there exists the edge {a, b} if the two elements can be compared, i.e. c(a, b) ̸=⊥. Moreover, we denote with q the number of missing edges, i.e. q = 􏰁|V |􏰂 − |E|. In this 2 setting we present the algorithm in [3] with O((q+n) log(n2/q)) query complexity and O(nω) time complexity, where ω is the exponent of the matrix multiplication. Lastly, we examine the special cases of chordal and comparability graphs, where we present an algorithm, also due to [3], with O(n log n) query and O(nω ) time complexity, re­ spectively.