Введение

В математической дисциплине теории графов, множество вершин обратной связи (FVS) графа — это набор вершин, удаление которых приводит к ациклическому графу (под "удалением" понимается удаление вершины и всех к ней прилегающих рёбер). Эквивалентно, любой FVS содержит хотя бы одну вершину из каждого цикла в графе. Число вершин обратной связи графа — это размер минимального FVS. Задача поиска минимального множества вершин обратной связи является NP-полной задачей; она была одной из первых задач, для которых доказана NP-полнота. Она имеет широкое применение в операционных системах, системах управления базами данных и проектировании интегральных схем (чипов) VLSI.

NP-жесткость

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

Точные алгоритмы

Соответствующая NP-задача оптимизации по нахождению размера минимального набора вершин обратной связи может быть решена за время O(1.7347n), где n — количество вершин в графе. Этот алгоритм фактически вычисляет максимальный индуцированный лес, и когда такой лес получен, его дополнение является минимальным набором вершин обратной связи. Количество минимальных наборов вершин обратной связи в графе ограничено величиной O(1.8638n). Задача о наборе вершин обратной связи для ориентированных графов все еще может быть решена за время O*(1.9977n), где n — количество вершин в заданном ориентированном графе. Параметризованные версии ориентированных и неориентированных задач являются фиксированно-параметрически разрешимыми. В неориентированных графах максимальной степени три задачу о наборе вершин обратной связи можно решить за полиномиальное время, сведя ее к экземпляру задачи о четности матроида для линейных матроидов.

Границы

Согласно теореме Эрдеша — Поша, размер минимального множества вершин обратной связи отличается от максимального числа непересекающихся циклов в данном графе не более чем логарифмический фактор.

Связанные понятия

Вместо вершин можно рассматривать множество рёбер обратной связи – набор рёбер в неориентированном графе, удаление которых делает граф ациклическим. Размер наименьшего множества рёбер обратной связи в графе называется рангом циклов графа. В отличие от числа FVS, ранг циклов можно легко вычислить: это , где C – множество связных компонент графа. Задача поиска наименьшего множества рёбер обратной связи эквивалентна задаче поиска остовного леса, которую можно решить за полиномиальное время. Аналогичным понятием в ориентированном графе является множество дуг обратной связи (FAS) – набор ориентированных дуг, удаление которых делает граф ациклическим. Поиск наименьшего FAS является NP-трудной задачей, а также связана с задачей переконфигурации путей.

Научно-исследовательские статьи

Да.