# Topological sorting and NP-hard proof

I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness.

The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,x_n\}$, a partial order $<$, where $x_i <x_j$ means that $x_i$ must be in front of $x_j$, and a new item $x_k$ as well as related statements $x_k<x_i$ for some $i$'s and $x_j<x_k$ for some $j$'s to be added to the partial order, how to find the least replacement solution to insert $x_k$ into the original sequence $X$ without violating the resulting partial order?

It can be ensured that the partial order forms no cycle such as $x_i<\cdots<x_j<\cdots <x_i$.

• What did you try? Where did you get stuck? What problems have you tried reducing from? We have some reference material here. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Mar 9 '18 at 1:56
• (1) How exactly do "replacements" work? What are their costs? (2) I suspect that when you wrote "a set of partial orders", you meant "a partial order" (a partial order is itself a set of pairs, not a single pair). – j_random_hacker Mar 9 '18 at 14:42
• What is "the least replacement solution"? Also, rather than responding in the comments, please edit the question to clarify. – D.W. Mar 9 '18 at 17:07
• @xskxzr: Thanks, I've made another edit now. – j_random_hacker Mar 9 '18 at 21:55

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:

1. $$x_k$$ with no constraints: put $$x_k$$ anywhere in the ordering.
2. $$x_k > x_i$$: put $$x_k$$ anywhere after $$x_i$$ in the ordering.
3. $$x_k < x_j$$: put $$x_k$$ anywhere before $$x_i$$ in the ordering.
4. $$x_i < x_k < x_j$$: put $$x_k$$ anywhere in between $$x_i$$ and $$x_j$$ in the ordering.
5. $$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:

1. Let $$A_i$$ be all elements reachable ("after") in the DFS starting at $$x_i$$ of the current partial ordering.
2. 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$$.
3. 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$$.
4. 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:
1. Move all elements in $$B_j$$ that are after $$x_i$$ in the ordering, before $$x_i$$.
2. Move all elements in $$A_i$$ that are before $$x_j$$ in the ordering, after $$x_j$$.
5. 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)$$.