# 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?