The key idea behind the algorithm is as follows: If we know a partition of the vertex set \(N\)  into relatively few sets which do not change their relative positions in the topological ordering, then we have a limited space of possible orderings which can be obtained by performing at most \(r\)  inversions. To specify which vertices keep their relative positions we employ a technique called color coding [1]}. Intuitively, we randomly color all vertices with \(\mathcal {O}(\sqrt{r})\)  colors in a way that vertices of the same color keep their relative positions. As the local search algorithm for FAST [2]}, our color coding algorithm is closely related to a subexponential time algorithm for FAST [3]}.
