Коротко сформулирую задачу и дам оценку сложности, практические эвристики и случаи, в которых есть полиномиальное решение.

Формулировка. Пусть (G=(V,E)) — ориентированный граф. Нужно найти минимальное множество рёбер (F\subseteq E) такое, что граф (G'=(V,E\setminus F)) не содержит ориентированных циклов (DAG). Эквивалентная формулировка: выбрать порядок вершин (\pi) минимизирующий число «обратных» рёбер
[
#{(u,v)\in E:\ \pi(v)<\pi(u)}.
]

Сложность.

Общая задача Minimum Feedback Arc Set (MFAS) в ориентированном графе NP‑полна (решение проверки «есть ли решение размера (\le k)» — NP‑полное). Соответственно, в общем случае полиномиального алгоритма маловероятно.Для общего ориентированного графа точные алгоритмы требуют экспоненциального времени (например, перебор/ветвление или ILP).Существуют параметризованные и экспоненциально‑временные алгоритмы, поэтому задача FPT по размеру решения (k) (есть алгоритмы с видом времени (f(k)\cdot \mathrm{poly}(n))) — практический путь, если требуемое число удаляемых рёбер невелико.

Практическая приближённая стратегия / эвристики для больших графов
(быстро, простые и часто дающие хорошие результаты):

1) Свести к упорядочиванию вершин:

Найти порядок вершин и удалить все «обратные» рёбра относительно этого порядка. Нужно хорошее приближение порядка.

2) Жадный порядок по разности степеней:

Повторно выбирать вершину с максимальной разностью ( \mathrm{outdeg}-\mathrm{indeg}) (или максимум по outdeg) и ставить её в начало/конец порядка; удалять её и обновлять степени. Это O(m+n)–O(m log n) на практике и часто даёт хорошее приближение.

3) DFS‑базовый базовый метод:

Запустить DFS, все back‑edges удалить. Быстро (O(n+m)), даёт корректный (но не оптимальный) набор рёбер.

4) Локальный поиск (pairwise swaps / 2‑opt):

Начальный порядок от жадного алгоритма, затем итеративно менять пары вершин (или мелкие перестановки), если это уменьшает число обратных рёбер. Часто существенно улучшает результат.

5) Спектральные / ранжирующие методы:

Использовать собственные вектора матриц смежности/Лапласиана, PageRank‑похожие ранжирования или решение релаксации (LP/SDP) и рандомизированное округление; более затратны, но часто лучше в тяжёлых случаях.

6) Удаление «наиболее вредных» рёбер:

Оценивать «вклад» рёбер в циклы (по числу обнаруженных простых циклов, по центральности в ориентированных циклах и т.д.) и жадно удалять наиболее вкладающие. Для больших графов оценки могут быть приближёнными (рандомизированные обходы, ограничение длины циклов).

7) Комбинации:

Сжать граф через конденсацию SCC (см. ниже), применять эвристику внутри сильных компонент, затем локальная доработка и ILP на оставшихся критичных частях.

Качество приближения и алгоритмическая сложность

Большинство простых эвристик линейны или близки к линейным по входу; локальные улучшения дают хорошие практические результаты.Для общего ориентированного графа гарантии аппроксимации ограничены; общая задача вряд ли допускает (полиномную) PTAS. Для специальных классов — см. ниже.

Случаи с точным полиномиальным решением

Непрерывно простые случаи:
Если (G) уже ацикличен — тривиально.Если подлежащий неориентированный граф — лес: ориентированное дерево не может содержать ориентированных циклов, значит задача тривиальна.Для неориентированного графа (если направление рёбер игнорируется) минимум рёбер, которые надо удалить чтобы получить лес, равен
[
|E|-(|V|-c),
]
где (c) — число компонент связности (решается полиномиально через остовные леса). Замечание: это не эквивалентно MFAS в общем ориентированном случае, потому что направление важно.Конденсация SCC:
Сначала сократить каждую сильную компоненту (SCC). Циклы находятся внутри SCC; между SCC циклов нет. Значит задача распадается на независимые подзадачи на каждой SCC. Если все SCC имеют размер, ограниченный постоянной (s), то перебор внутри каждой SCC работает за полиномиальное время (константная сложность на компоненты) — следовательно, в этом случае задача полиномиальна.Ограничение параметров:
Если искомое число удаляемых рёбер (k) мало, можно применять FPT‑алгоритмы: время вида (f(k)\cdot \mathrm{poly}(n)). Тогда задача практически решаема для небольших (k).Специализированные классы:
Для турниров (ориентирование полного графа) известны более сильные приближения (напр., PTAS в литературе); это частный класс, где алгоритмы аппроксимации хорошо работают. (Точные полиномиальные алгоритмы для произвольных турниров в общем случае отсутствуют.)Для некоторых структурированных графов (ограниченная ширина разреза, bounded treewidth/feedback‑width с учётом ориентации) можно получить DP‑алгоритмы — полиномиальные при фиксированной ширине.

Рекомендация для практики

Сжать граф по SCC.На каждой большой SCC: получить начальный порядок жадно (разность степеней), затем локальный поиск (swaps), — удалять обратные рёбра.Если осталось небольшое число противоречий или компонент небольшие, решить точно ILP/FPT на этих частях.Для экстремально больших графов использовать многопроходные эвристики (локальные улучшения + случайные рестарты) и/или спектральные методы.

Если нужно, могу дать псевдокод конкретной эвристики (жадный порядок + 2‑opt) и оценку её временной сложности.