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

В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин➤ является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.

Определение

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

Дано: (Неориентированный или ориентированный) граф ${\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}$, является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего циклы множества вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).

NP-трудность

Карп^[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].