I guess this optimality depends on how you define "the least replacement solution". I'm taking it to mean minimum insertions / deletions. If you prefer minimum number of swaps necessary, take a look at step 4.1 and 4.2 and you may be able to optimize it for such, though I don't show it here.
If it is ensured that no additional $x_k$ and its partial constraints will cause a cycle, then this becomes relatively easy. Consider a topological ordering $\{x_1, x_2, \ldots, x_i, \ldots, x_j, \ldots\}$ where $x_i$ and $x_j$ have no transitive relation. We now have five options for additional constraints to be added:
- $x_k$ with no constraints: put $x_k$ anywhere in the ordering.
- $x_k > x_i$: put $x_k$ anywhere after $x_i$ in the ordering.
- $x_k < x_j$: put $x_k$ anywhere before $x_i$ in the ordering.
- $x_i < x_k < x_j$: put $x_k$ anywhere in between $x_i$ and $x_j$ in the ordering.
- $x_j < x_k < x_i$: this is the only case where we will need to rearrange existing nodes because $x_i$ and $x_j$ are out of order currently.
For case 5 we will first worry about the fact that we are transitively adding an edge $x_j < x_i$, then after re-ordering, this will resolve to case 4. Do the following:
- Let $A_i$ be all elements reachable ("after") in the DFS starting at $x_i$ of the current partial ordering.
- Let $B_j$ be all elements on any path from the root to $x_j$. This can be computed in linear time by doing a DFS on the reverse partial ordering, starting at $x_j$.
- Note that if $x_j \in A_i$ then this violates our original assumption. If $x_i \in B_j$, this also violates our original assumption. So we know $x_j \not\in A_i$ and $x_i \not\in B_j$.
- Greedily move all elements in $B_j$ before all elements in $A_i$. This can be done by doing one of the following which has minimum insertions:
- Move all elements in $B_j$ that are after $x_i$ in the ordering, before $x_i$.
- Move all elements in $A_i$ that are before $x_j$ in the ordering, after $x_j$.
- You can show that the minimum of these two will be a lower bound for the number of insertions / moves necessary.
After you have separated $B_j$ into the first half of the order and $A_i$ into the second half, this case reduces to case 4 as described above. Overall this will take $O(n + m)$.