Finding longest chain in poset in subquadratic time 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 &lt; a_1 &lt; \cdots &lt; 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$.
Well, start by observing that

when A has no comparable pairs, the height will be 0
and
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' &lt; a$ ​ and $a$'s right list is the $a'$ such that ​ $a &lt; 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.