# On finding a chain decomposition of a Partial Order

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?

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.
• @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. – Sasho Nikolov Sep 18 '11 at 21:56