Предлагается основываться на алгоритме MNR (в этой статье хорошо описан), который изменяет топологический порядок не на всем графе, а только на необходимом участке. Возможно, стоит посмотреть в сторону других алгоритмов.
На текущий момент инструмент Dl-Check (https://github.com/Devexperts/dlcheck) использует его для поиска циклов в графе блокировок (см. pre-print прикрепленной статьи). Для корректной синхронизации используется ReadWriteLock следующим образом: при чтении значения топологического порядка используется ReadLock, а при его изменении – WriteLock. Таким образом, при изменении топологического порядка происходит практически stop the world, а меняется он не быстро судя по собранной статистике. Предлагается оптимизировать эту часть.