В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.
Определение Задача о разрезающем циклы множестве вершин — это следующая задача разрешимости:
Дано: (Неориентированный или ориентированный) граф и положительное число . Вопрос: Существует ли подмножество , для которого , такой, что с удалёнными вершинами, принадлежащими , не содержит циклов?
Граф , оставшийся после удаления из графа вершин, принадлежащих множеству , является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего циклы множества вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).
NP-трудность Карп показал, что задача о разрезающем циклы множестве вершин для ориентированных графов является NP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трёмНеопубликованный результат, принадлежащий Гарей и Джонсону (Garey, Johnson), см. : GT7. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графах, и задача остаётся NP-трудной на графах с максимальной степенью четыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах с максимальной степенью, не превосходящей трёх.
Заметим, что задача удаления как можно меньшего числа рёбер для разрыва циклов (в неориентированном графе) эквивалентна нахождению остовного дерева, и эта задача может быть выполнена за полиномиальное время. В противоположность этому задача удаления рёбер из ориентированного графа с целью сделать его ациклическим, то есть задача о разрезающем циклы наборе дуг, является NP-полной.
Точные алгоритмы Соответствующая NP-полная оптимизационная задача нахождения размера минимального разрезающего циклы множества вершин может быть решена за время O(1,7347n), где n — число вершин в графе . Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограничено O(1,8638n). Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за время O*(1,9977n), где n — число вершин в данном ориентированном графе. Параметризованные версии ориентированной и неориентированной задач .
Приближение Задача является APX-полной, что прямо следует из APX-сложности задачи о вершинном покрытии и существования аппроксимации, сохраняющей L-приведение из задачи о вершинном покрытии к этой задаче. Лучший известный алгоритм для неориентированных графов имеет коэффициент два. См. также для альтернативного аппроксимационного алгоритма с тем же коэффициентом..
Границы Согласно теореме Эрдёша — Поза размер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графе.
Приложения В операционных системах разрезающее циклы множество вершин играет заметную роль в обнаружении взаимных блокировок (deadlock). В графе ожидания операционной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прервать
Кроме того, разрезающее циклы множество вершин имеет приложение в разработке СБИС.
Примечания
Литература
Исследовательские статьи и книги
.
Учебники и обзорные статьи
Категория:NP-полные задачи Категория:Вычислительные задачи теории графов