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

Втеории графовразрезающее циклы множество вершинграфа— это множество вершин, удаление которых приводит к разрывуциклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа.
Задача о разрезающем циклы множестве вершин➤является втеории вычислительной сложностиNP-полнойзадачей. Задача входит в список21 NP-полных задач Карпа. Задача имеет широкое применение воперационных системах,базах данныхи разработкеСБИС.
Задача о разрезающем циклы множестве вершин— это следующаязадача разрешимости:
ГрафG[V∖X]{\displaystyle G[V\setminus X]}, оставшийся после удаления из графаG{\displaystyle G}вершин, принадлежащих множествуX{\displaystyle X}, является порождённымлесом(для неориентированных графов, или порождённымнаправленным ациклическим графомдляориентированных графов). Таким образом, поиск минимального разрезающего циклы множества вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случаеориентированных графов).
Карппоказал, что задача о разрезающем циклы множестве вершин дляориентированных графовявляетсяNP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трём. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графах, и задача остаётся NP-трудной на графах смаксимальной степеньючетыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах смаксимальной степенью, не превосходящей трёх.
Заметим, что задача удаления как можно меньшего числарёбердля разрыва циклов (в неориентированном графе) эквивалентна нахождениюостовного дерева, и эта задача может быть выполнена заполиномиальное время. В противоположность этому задача удаления рёбер изориентированногографас целью сделать егоациклическим, то есть задачао разрезающем циклы наборе дуг, является NP-полной.
СоответствующаяNP-полная оптимизационная задачанахождения размера минимального разрезающего циклы множества вершин может быть решена за времяO(1,7347), гдеn— число вершин в графе. Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограниченоO(1,8638). Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за времяO*(1,9977), гдеn— число вершин в данном ориентированном графе. Параметризованные версии ориентированной и неориентированной задачфиксированно-параметрически разрешимы.
Задача являетсяAPX-полной, что прямо следует из APX-сложностизадачи о вершинном покрытиии существования аппроксимации, сохраняющейL-приведениеиз задачи о вершинном покрытии к этой задаче. Лучший известный алгоритм для неориентированных графов имеет коэффициент два.
Согласнотеореме Эрдёша — Позаразмер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графе.
Воперационных системахразрезающее циклы множество вершин играет заметную роль в обнаружениивзаимных блокировок(deadlock). Вграфе ожиданияоперационной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прервать
Кроме того, разрезающее циклы множество вершин имеет приложение в разработкеСБИС.