Алгоритм (две практичные схемы: простая эвристика и полиномиально-аппроксимация через LP/Set‑Cover).
1) Простая эвристика "удалять вершину из найденного цикла"
- Описание:
- Пока граф содержит ориентированный цикл:
- Найти любой ориентированный простой цикл $C$ (DFS).
- Выбрать в $C$ вершину $v$ по некоторому критерию (например, максимальная степень ${\mathrm{deg}}^{+}(v)+{\mathrm{deg}}^{-}(v)$ или максимальное число входящих/исходящих ребер внутри текущего графа) и удалить её.
- Сложность: поиск цикла $O(n+m)$; до $n$ итераций $\Rightarrow O(n(n+m))$.
- Свойства:
- Практически прост и часто хорошо работает на реальных (разреженных, с локализованными циклами) графах.
- Формальных гарантированных константных аппроксимаций нет: в худшем случае качество может быть очень плохим (примерно до $\Theta (n)$ по отношению к оптимуму).
- Лучшие случаи: небольшие или локализованные циклы, когда удаление вершины разрывает много циклов одновременно. Худшие: графы, где циклы перекрываются так, что каждая удалённая вершина уничтожает мало циклов.
2) LP / сведение к Set‑Cover — полиномиальная аппроксимация $O(\log n)$ - Формулировка покрытия циклов:
- Вводим переменные $x_v\in [0,1]$ для каждой вершины $v$. Для каждой ориентированной простого цикла $C$ накладываем ограничение ${\sum }_{v\in C}{x}_v\ge 1$. Минимизируем ${\sum }_v{x}_v$.
- Это точное дробное релаксация задачи попадания (hitting) во все циклы (аналог Set‑Cover).
- Решение LP:
- Число ограничений (циклов) экспоненциально, но существуют разделяющие оракулы: для заданного вектора $x$ можно за полиномиальное время найти цикл $C$ с ${\sum }_{v\in C}{x}_v<1$ или доказать их отсутствие, сведя задачу к поиску кратчайшего цикла по вершн‑весам (путём присваивания ребру $(u\to v)$ веса $x_v$ и поиска цикла малого суммарного веса).
- Следовательно LP можно решать эллипсоидой/методом грубой итерации разделяющего оракула за полиномиальное время.
- Округление и аппроксимация:
- Классическое округление для Set‑Cover — жадное или случайное с масштабированием даёт фактор $H_t\le 1+\ln t$, где $t$ — число множеств (можно оценивать через $n$). Случайное округление: взять каждую вершину с вероятностью $\min (1,c\cdot x_v\ln n)$ с подходящим константным $c$; затем дополнять жадно оставшиеся невложенные циклы. Это даёт аппроксимацию $O(\ln n)$ относительно оптимума LP (и следовательно оптимума целочисленного решения).
- Формально: если $OPT$ — размер оптимального FVS и $x^{\ast }$ — оптимум LP, то после округления ожидаемый размер множества $S$ удовлетворяет $\mathbb{E}[|S|]\le O(\ln n)\cdot x^{\ast }\le O(\ln n)\cdot OPT$.
- Сложность: решение LP с разделяющим оракулом полиномиально (примерно полином в $n,m$ с логарифмическими множителями); практическая реализация сложнее и дороже, чем простая эвристика.
- Свойства и ограничения:
- Гарантированная аппроксимация $O(\ln n)$. Для некоторых реализаций достигают $O(\ln n\cdot \ln \ln n)$ или улучшений с более тонкой техникой, но нижняя граница через интегральный разрыв Set‑Cover даёт, что полное избавление от лог‑фактора требует существенных новых идей.
- Лучшие случаи: графы, где дробный релакс даёт близкое к целому решение (малый интегральный разрыв). Худшие: специально сконструированные графы, где интегральный разрыв достигает $\Theta (\ln n)$ — тогда алгоритм близок к худшему возможному для этого подхода.
Краткие рекомендации
- Для практики и больших графов — начать с эвристики (п.1); она быстра и часто даёт хорошие решения.
- Если важна теоретическая гарантия — использовать LP/Set‑Cover подход (п.2) для $O(\ln n)$-аппроксимации, понимая, что он дороже и в худшем случае даёт логарифмический множитель от оптимума.
- Замечание: для специальных классов графов (напр., ациклические по структуре, турниры, графы с ограниченной шириной деревьев и т.п.) существуют более сильные алгоритмы/полиаппроксимации; в общем ориентированном случае задача трудноаппроксимируема и простых константных аппроксимаций нет.