# 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. Posted on Categories Articles