I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532

In that paper it is presented an enhancement to the algorithm Poset-BinInsertionSort by Faigle & Turan (Figure 1 in the paper) for the reconstruction of a partial order when we are allowed to invoke an oracle telling us if two elements are related or not. The enhancement consists in replacing a step of the previous algorithm with a less expensive step (Figure 2: the EntropySort algorithm).

Now, here's the question. The complexity, in terms of number of queries to the oracle, of the Feigle & Turan algorithm is $O(wn \log n)$ for a poset of width $w$ made up of $n$ elements. (For definitions please see the paper's introduction)

Algorithm in Figure 1 proceeds by incrementally adding one element at a time and in step 4.c it asks for finding a chain decomposition of the set of elements considered so far. I'm struggling with this point because, even if we keep the chain decomposition up-to-dated I am not able to reduce the number of queries to $O(\log n)$ as it would have been requested to keep the complexity of $O(n \log n + wn)$ as claimed in theorem 6 of the paper.

In brief, here's the question. Suppose you are given a Poset $P=(A,R)$ of width w (i.e. the cardinality of the largest antichain is w) suppose you have $A^\prime \subseteq A$. Is it possible to build a decomposition of size $q \leq w$ in time $O(\log n)$ queries as requested by the algorithm in the paper?

Thanks in advance. f


1 Answer 1


Your access to $A$ (which is $P$ in the paper) is through an oracle, and you're charged for each query. But in terms of the query count, your accesses to $A'$ (which is $P'$ in the paper and is an "induced sub-poset" of $A$) are free. So the answer is that a chain decomposition of $A'$ is built without asking any new queries to $A$, only based on the relations in $A'$, which are already known. Then a new element is inserted by performing a binary search on each chain of the chain decomposition, and this is where $w\log n$ queries are performed.

Note that Theorem 6 relates to Figure 2 and not Figure 1. There the number of queries is decreased by querying asymptotically optimally, rather than blindly doing a binary search independently on each chain (which would ignore relations going between chains).

  • $\begingroup$ Right... thanks! I was about to remove the question as I spotted this already. Stupid question, I know :))) $\endgroup$ Commented Sep 16, 2011 at 7:57
  • $\begingroup$ Not a stupid question, and a very interesting papers. Could it be improved to consider the difference between a partial order with two completely uncomparable chains of equal lenght and a partial order with only one uncomparable element? $\endgroup$
    – J..y B..y
    Commented Sep 18, 2011 at 20:00
  • $\begingroup$ @Jeremy: good question. their algorithm is asymptotically optimal w.r.t. comparisons when the width $w$ satisfies $w = o(n/\log n)$. I wonder if finding a comparison strategy optimal for the whole range of $w$ is open. And also an optimal strategy that is efficiently computable (even their optimal strategy for $w = o(n/\log n)$ is not efficiently computable). Similar question have been considered for sorting with partial information. $\endgroup$ Commented Sep 18, 2011 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.