<p>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&#39;$ (which is $P&#39;$ in the paper and is an "<em>induced</em> sub-poset" of $A$) are free. So the answer is that a chain decomposition of $A&#39;$ is built without asking any new queries to $A$, only based on the relations in $A&#39;$, 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. </p>

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

CC BY-SA 3.0
2011-09-16T07:57:00.343Z
Right... thanks! I was about to remove the question as I spotted this already. Stupid question, I know :)))
Fabrizio Silvestri
CC BY-SA 3.0
2011-09-18T20:00:59.037Z
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?
J.y B.y
CC BY-SA 3.0
2011-09-18T21:56:56.020Z
@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
CC BY-SA 3.0
2011-09-16T05:12:22.423Z
2011-09-16T05:12:22.423Z
Sasho Nikolov
<p>I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". <a href="http://arxiv.org/abs/0707.1532" rel="nofollow">http://arxiv.org/abs/0707.1532</a></p>

<p>In that paper it is presented an enhancement to the algorithm Poset-BinInsertionSort by Faigle &amp; 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).</p>

<p>Now, here's the question. The complexity, in terms of number of queries to the oracle, of the Feigle &amp; 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)</p>

<p>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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>Thanks in advance.
f</p>

<ds.algorithms><partial-order><order-theory>
On finding a chain decomposition of a Partial Order
Fabrizio Silvestri
# On finding a chain decomposition of a Partial Order

(Asked by: username_0 on 2011-09-15)

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

**Tags:** ds.algorithms, partial-order, order-theory

---

## 1 answers

### Answer by username_1 on 2011-09-16. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: Right... thanks! I was about to remove the question as I spotted this already. Stupid question, I know :)))  
> **username_2**: 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?  
> **username_1**: @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.  

---

