Let $(A,\leq)$ be some finite poset. For $a,a' \in A$ we can determine in constant time whether or not $a \leq a'$. The height of an $A$ is by definition the greatest $n$ such that there are elements $$ a_0 < a_1 < \cdots < a_n $$ of $A$. By treating $(A,\leq)$ as a directed acyclic graph, we can determine the height of $A$ as the length of the longest path in this graph, which we can compute in linear time in the size of the graph; that is, in $\mathcal O(|A|^2)$.

Can we do any better for this special case where $A$ is a poset?

Edit: if it matters, I am especially interested in the case where the length of the longest path is already known to be significantly shorter than the size of $A$.

  • 1
    $\begingroup$ Are you sure you have a partially ordered set? You mention that for $a, a' \in A$ you have an order. Is that for all $a, a'$ or? $\endgroup$
    – orlp
    Commented Dec 24, 2016 at 16:01
  • $\begingroup$ @orlp, for all $a,a'$ we can determine whether or not $a \leq a'$; but if we find $a \not \leq a'$ that does not mean that $a' \leq a$ must hold. Obviously the question does not make sense when $A$ is totally ordered, as then the answer is always $|A|-1$. $\endgroup$ Commented Dec 24, 2016 at 19:15
  • $\begingroup$ Maybe I'm still misunderstanding exactly what you meant. Either way I undeleted my answer, but if it's not correct because of some wrong assumption feel free to comment on it explaining why and I'll delete it. $\endgroup$
    – orlp
    Commented Dec 25, 2016 at 8:11
  • $\begingroup$ @orlp, as also pointed out by chi, I am not sure where you are getting the total order from. The set $A$ is typically not totally ordered. The only thing I mention in my post is that the partial order relation $\leq$ is decidable in constant time, which has nothing in particular to do with totality. $\endgroup$ Commented Dec 25, 2016 at 11:10

1 Answer 1


Well, start by observing that

when A has no comparable pairs, the height will be 0
when A has one or two comparable pairs, the height will be 1


Thus, when ​ $\leq$ ​ is given with one bit for each ordered-pair of distinct elements,
even promised-to-be-at-most-1 height will have
co-nondeterministic query complexity ​ $(|\hspace{.02 in}A|\hspace{-0.03 in}\cdot \hspace{-0.03 in}(|\hspace{.02 in}A|\hspace{-0.04 in}-\hspace{-0.05 in}1))\hspace{.02 in}/\hspace{.02 in}2$
and probabilistic query complexity ​ $\Theta$$\left(\hspace{-0.02 in}|\hspace{.02 in}A|^2\right)$ .

Accordingly, we can only hope for better when ​ $\leq$ ​ is given in some other way,
like as a list of the pairs for which it's true or as

an $A$-indexed array of ordered-pairs of lists, such that for each element $a$ of $A$,
$a$'s left list is the $a'$ such that ​ $a' < a$ ​ and $a$'s right list is the $a'$ such that ​ $a < a'$


(I currently have no clue regarding the complexity for such representations of ​ $\leq$ .)

For your case of interest:

See this question and its answer.
(That answer's universe size is your n and that answer's n is your ​ $|\hspace{.04 in}A|$ .)

However, that negative result does not necessarily apply to
"the case where the length of the longest path is already known to be" short.

  • $\begingroup$ Thank you! Actually, my case of interest had more structure (it is a subset of the boolean algebra $\{0,1\}^n$ with the induced ordering -- that is, a set of bit strings ordered pointwise) but it didn't immediately seem relevant to me. With this answer I see that I really need to dive into the structure of the kind of $A$ I care about. $\endgroup$ Commented Dec 24, 2016 at 22:20
  • $\begingroup$ (I just edited my answer, and don't know whether-or-not stackexchange will inform you of that.) ​ ​ $\endgroup$
    – user12859
    Commented Dec 25, 2016 at 4:30
  • $\begingroup$ Thank you for the update, but they are talking about anti-chains while I am talking about chains -- or is there a symmetry that I am missing? $\endgroup$ Commented Dec 25, 2016 at 11:07
  • $\begingroup$ By definition, a set $S$ is an anti-chain if and only if there are no elements ​ $a_0,a_1$ ​ of $S$ such that ​ $a_0 < a_1$ . ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Dec 25, 2016 at 17:46

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.