On finding a chain decomposition of a Partial Order

Question

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

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).