patternMinor
Finding longest chain in poset in subquadratic time
Viewed 0 times
subquadraticposettimefindinglongestchain
Problem
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$.
$$
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$.
Solution
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.
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.
Context
StackExchange Computer Science Q#67847, answer score: 3
Revisions (0)
No revisions yet.