6
$\begingroup$

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

$\endgroup$
  • 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 Dec 24 '16 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$ – Mees de Vries Dec 24 '16 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 Dec 25 '16 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$ – Mees de Vries Dec 25 '16 at 11:10
3
$\begingroup$

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



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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.