# 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 < 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$.

• 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?
– orlp
Dec 24 '16 at 16:01
• @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$. Dec 24 '16 at 19:15
• 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.
– orlp
Dec 25 '16 at 8:11
• @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. Dec 25 '16 at 11:10

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

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.

• 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. Dec 24 '16 at 22:20
• (I just edited my answer, and don't know whether-or-not stackexchange will inform you of that.) ​ ​
– user12859
Dec 25 '16 at 4:30
• 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? Dec 25 '16 at 11:07
• 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$ . ​ ​ ​ ​
– user12859
Dec 25 '16 at 17:46