Edge ranking and searching in partial orders

AbstractWe consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n4log3n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an O(lognlog(logn))-approximate polynomial-time algorithm for this problem