# Series-parallel extension of a partial order respecting a given total order

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.

An $O(n^3)$ dynamic programming algorithm suggests itself, solving the problem in increasing intervals of $R$, starting from empty intervals and terminating with the whole $R$. Is it possible to solve the problem in subcubic time?

• What do you mean by the "length" of the partial order $Q$?
– a3nm
Jan 21 '18 at 14:11
• Length is the number of elements in the longest chain mathworld.wolfram.com/PartialOrderLength.html Jan 21 '18 at 17:52