Топологический вид циклического графа с минимальным количеством нарушенных ребер

Question

Я ищу способ выполнить топологическую сортировку по заданному невзвешенному графику, содержащему циклы. Результат должен содержать не только упорядочение вершин, но и множество ребер, нарушаемых данным упорядочением. Этот набор ребер должен быть минимальным.

Поскольку мой входной график потенциально большой, я не могу использовать алгоритм экспоненциального времени. Если невозможно вычислить оптимальное решение в полиномиальное время, какая эвристика была бы разумной для данной проблемы?

Answer 1

Eades, Lin, and Smyth предлагается A fast and effective heuristic for the feedback arc set problem. Оригинальная статья находится за платной линией, но бесплатная копия доступна с here.

Существует алгоритм топологической сортировки, который строит порядок вершин, выбирая вершину без входящих дуг, рекурсивную на графе минус вершина и добавляя эту вершину к порядку. (Я описываю алгоритм рекурсивно, но вам не нужно его реализовать таким образом.) Алгоритм Eades-Lin-Smyth также ищет вершины без исходящих дуг, а присоединяет их. Конечно, может случиться, что все вершины имеют входящую и исходящую дуги. В этом случае выберите вершину с наивысшим разницей между входящим и исходящим. Здесь, несомненно, есть место для экспериментов.

Алгоритмы с доказуемым наихудшим поведением основаны на линейном программировании и графах. Они опрятные, но гарантии менее идеальны (log^2 n или log n log log n раз столько, сколько необходимо), и я подозреваю, что эффективные реализации были бы довольно проектом.