Разрезающее циклы множество вершин

Задача о разрезающем циклы множестве вершин — это следующая задача разрешимости:

Дано: (Неориентированный или ориентированный) граф ${\displaystyle G=(V,E)}$ и положительное число ${\displaystyle k}$.

Вопрос: Существует ли подмножество ${\displaystyle X\subseteq V}$, для которого ${\displaystyle |X|\leq k}$, такой, что ${\displaystyle G}$ с удалёнными вершинами, принадлежащими ${\displaystyle X}$, не содержит циклов?

Граф ${\displaystyle G[V\setminus X]}$, оставшийся после удаления из графа ${\displaystyle G}$ вершин, принадлежащих множеству ${\displaystyle X}$, является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего цикла множество вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).

Карп[1] показал, что задача о разрезающем циклы множестве вершин для ориентированных графов является NP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трём[2]. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графов, и задача остаётся NP-трудной на графах с максимальной степенью четыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах с максимальной степенью, не превосходящей трёх[3][4].

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

Соответствующая NP-полная оптимизационная задача нахождения размера минимального разрезающего циклы множества вершин может быть решена за время O(1,7347ⁿ), где n — число вершин в графе [5]. Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограничено O(1,8638ⁿ)[6]. Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за время O*(1,9977ⁿ), где n — число вершин в данном ориентированном графе[7]. Параметризованные версии ориентированной и неориентированной задач фиксированно-параметрически разрешимы[8].

Задача является APX-полной, что прямо следует из APX-сложности задачи о вершинном покрытии[9] и существования аппроксимации, сохраняющей L-приведение из задачи о вершинном покрытии к этой задаче[1]. Лучший известный алгоритм для неориентированных графов имеет коэффициент два[10].

Согласно теореме Эрдёша — Поза размер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графе[11].

В операционных системах разрезающее циклы множество вершин играет заметную роль в обнаружении взаимных блокировок (deadlock). В графе ожидания операционной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прервать[12]

Кроме того, разрезающее циклы множество вершин имеет приложение в разработке СБИС[13].