Метод вырезания узлов¶

Метод вырезания узлов — в теории графов и комбинаторной оптимизации совокупность алгоритмических приёмов, позволяющих свести задачу на графе к задаче на графе меньшего размера путём удаления вершины и последующего восстановления решения. Метод применяется при решении задач о независимом множестве, доминирующем множестве, раскраске, а также в алгоритмах точного решения NP-трудных задач с экспоненциальной оценкой времени работы.

¶Общая схема

Метод вырезания узлов основан на рекурсивном переборе. Для заданного графа \(G\) и параметра \(k\) (например, размера искомого множества) выбирается вершина \(v\), после чего задача решается для двух случаев: вершина \(v\) включается в искомое множество (и тогда удаляются \(v\) и её соседи) либо исключается (удаляется только \(v\)). Полученные подзадачи решаются рекурсивно, а из их результатов выбирается оптимальный. Такой подход носит название «метод ветвей и границ» (branch and bound) или «метод ветвей и отсечений».

Ключевая особенность — использование правил редукции: если граф содержит вершину малой степени, её можно обработать без ветвления, что сокращает дерево перебора. Для задач о вершинном покрытии и независимом множестве применяется правило: вершина степени 1 всегда включается в покрытие (или исключается из независимого множества), а вершина степени 0 удаляется.

¶Применение

¶Задача о вершинном покрытии

Для задачи о вершинном покрытии метод вырезания узлов даёт простейший алгоритм: если в графе есть вершина степени 0, она удаляется; если степени 1 — она и её сосед добавляются в покрытие; иначе выбирается вершина степени не менее 2, и происходит ветвление. В результате получается рекуррентное соотношение \(T(n) = T(n-1) + T(n-2)\), что даёт оценку \(O(1{,}618^n)\). Современные алгоритмы с более тонкими правилами редукции достигают оценок \(O(1{,}274^n)\).

¶Задача о независимом множестве

Независимое множество дополняет вершинное покрытие до полного графа, поэтому алгоритмы вырезания узлов применяются симметрично. Для вершин степени 1 независимое множество гарантированно содержит саму вершину, но не её соседа; для вершин степени 2 возможны дополнительные правила, сокращающие перебор.

¶Задача о доминирующем множестве

Для доминирующего множества метод усложняется: при включении вершины в решение удаляются она и все её соседи, при исключении — только она, но её соседи должны быть доминированы иначе. Используются правила для вершин степени 1 и 2, а также для пар смежных вершин малой степени. Оценка времени — \(O(1{,}4969^n)\) для общего случая.

¶Оценка сложности

Точное время работы зависит от правил ветвления. Для каждого правила составляется рекуррентное уравнение вида \(T(n) \le \sum T(n - d_i)\), где \(d_i\) — число удаляемых вершин в каждом случае. Решение уравнения даёт основание \(c\), и итоговая сложность — \(O(c^n)\). Поиск оптимальных правил ветвления — отдельная задача, решаемая с помощью компьютерного перебора (метод «мера и завоевание», measure and conquer).

¶Связь с другими методами

Метод вырезания узлов является частным случаем метода ветвей и границ, но в отличие от классической схемы, где отсечение происходит по оценке, здесь ветвление ведётся по конкретной вершине. Метод лежит в основе параметризованных алгоритмов (fixed-parameter tractable, FPT), где сложность оценивается как \(O(f(k) \cdot n^{O(1)})\), и используется при построении ядер (kernelization) — процедур сжатия графа до размера, зависящего только от параметра.

¶Ограничения

Метод эффективен для графов с малым числом вершин (до нескольких десятков) или для графов специального вида (деревья, кактусы, графы ограниченной древесной ширины). Для произвольных графов большой размерности он неприменим из-за экспоненциального роста времени. На практике метод комбинируют с эвристиками: сначала строят приближённое решение, затем используют его для отсечения ветвей в дереве перебора.

¶Примечания

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

¶Источники

• Ф. В. Фомин, Д. Крач, «Точные экспоненциальные алгоритмы», 2013.
• R. Niedermeier, «Invitation to Fixed-Parameter Algorithms», 2006.
• J. Chen, I. A. Kanj, G. Xia, «Improved Upper Bounds for Vertex Cover», 2010.