complexity theory – How to check effeciently that some changes preserve the topological ordering?


I have an acyclic directed graph with $k$ connected components. I also have a topological ordering $L$ (a sequence of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering).

So, let’s say for example $L = i_0,i_1,..,i_n$.

I have the following operations:

  1. Exchange(i,j): it simply exchange the positions of i and j in the list. Meaning that $L = ..,i,..,j,..$ becomes $L’=..,j,..,i..$

  2. Inserting(i,p): it simply remove $i$ from its position and inserts it in position $p$. Meaning that we have $L=a,b,c,i,d,e,f$ then inserting(i,6) gives $L”=a,b,c,d,e,i,f$.

Now how to check that $L’$ and $L”$ are also valid topological sorting? Apart from doing a graph traversal of course because I want to exploit the two facts: i) the graph comes in $k$ connected components and ii) some parts of $L$ remain unchanged in $L’$ and $L”$ so its not useful to check them. Please consider indicating the complexity of your approaches.