В математической дисциплине теории графов , множество вершин обратных (ПВС) из графа представляет собой набор вершин, удаление листьев граф без циклов ( «удаление» означает удаление вершины и все ребра , примыкающие к ней). Эквивалентно, каждый FVS содержит по крайней мере одну вершину любого цикла в графе. Номер набора вершин обратной связи графа - это размер наименьшего набора вершин обратной связи. Задача о множестве вершин с минимальной обратной связью является NP-полной задачей; это была одна из первых задач, NP-полная . Имеет широкое применение в операционных системах ,системы баз данных и проектирование микросхем СБИС .
Определение
Проблема решения FVS заключается в следующем:
- ЭКЗЕМПЛЯР: (неориентированный или направленный) граф. и положительное целое число .
- ВОПРОС: Есть ли подмножество с участием такое, что когда все вершины и их смежные края удаляются из , остаток без цикла ?
График что остается после удаления из является индуцированным лесом (соответственно, индуцированным ориентированным ациклическим графом в случае ориентированных графов ). Таким образом, поиск минимального FVS в графе эквивалентен нахождению максимального индуцированного леса (соответственно, максимального индуцированного ориентированного ациклического графа в случае ориентированных графов ).
NP-твердость
Карп (1972) показал, что задача минимума FVS для ориентированных графов является NP-полной . Проблема остается NP-полной для ориентированных графов с максимальными входящими и исходящими степенями два, а также для ориентированных плоских графов с максимальными входными и исходящими степенями три. [1]
Редукция Карпа также подразумевает NP-полноту проблемы FVS на неориентированных графах, где проблема остается NP-сложной на графах максимальной четвертой степени . Задачу FVS можно решить за полиномиальное время на графах максимальной степени не более трех. [2]
Точные алгоритмы
Соответствующая задача оптимизации NP по нахождению размера минимального набора вершин обратной связи может быть решена за время O (1,7347 n ), где n - количество вершин в графе. [3] Этот алгоритм фактически вычисляет максимальный индуцированный лес, и когда такой лес получается, его дополнением является минимальный набор вершин обратной связи. Количество минимальных наборов вершин обратной связи в графе ограничено O (1.8638 n ). [4] Задача о множестве вершин с направленной обратной связью все еще может быть решена за время O * (1.9977 n ), где n - количество вершин в данном ориентированном графе. [5] Параметризованные версии направленных и ненаправленных задач являются управляемыми с фиксированными параметрами . [6]
В неориентированных графах максимальной степени три проблема множества вершин обратной связи может быть решена за полиномиальное время , преобразовав ее в пример задачи четности матроидов для линейных матроидов . [7]
Приближение
Ненаправленная проблема APX-полная . Это следует из следующих фактов.
- APX-полнота проблемы вершинного покрытия ; [8]
- Существование приближения, сохраняющего L-редукцию от задачи о вершинном покрытии к ней;
- Существующие алгоритмы аппроксимации постоянного фактора. [9]
Самый известный алгоритм приближения на неориентированных графах - двукратный. [10]
Является ли ориентированная версия полиномиальной аппроксимацией по времени с постоянным соотношением и, следовательно, APX-полной, остается открытым вопросом.
Границы
Согласно теореме Эрдеша – Посы , размер минимального набора вершин обратной связи находится в пределах логарифмического множителя максимального числа вершинно-непересекающихся циклов в данном графе. [11]
Связанные понятия
- Вместо вершин можно рассматривать множество ребер обратной связи - множество ребер в неориентированном графе, удаление которых делает граф ацикличным. Размер наименьшего набора ребер обратной связи в графе называется рангом схемы графа. В отличие от числа FVS, ранг схемы можно легко вычислить: это, где C - множество компонент связности графа. Задача поиска наименьшего набора ребер обратной связи эквивалентна поиску остовного леса , что может быть выполнено за полиномиальное время .
- Аналогичным понятием в ориентированном графе является набор дуг обратной связи (FAS) - набор ориентированных дуг, удаление которых делает граф ацикличным. Найти самый маленький FAS - это NP-сложная задача. [9]
Приложения
- В операционных системах наборы вершин обратной связи играют важную роль в изучении восстановления из тупиковых ситуаций . В графе ожидания операционной системы каждый направленный цикл соответствует ситуации тупика. Чтобы разрешить все взаимоблокировки, необходимо прервать некоторые заблокированные процессы. Минимальная вершина обратной связи, установленная в этом графе, соответствует минимальному количеству процессов, которые необходимо прервать. [12]
- Проблема набора вершин обратной связи находит применение в разработке микросхем СБИС . [13]
- Другое приложение - теория сложности. Некоторые вычислительные задачи на графах в целом NP-трудны, но могут быть решены за полиномиальное время для графов с ограниченным числом FVS. Некоторыми примерами являются изоморфизм графов [14] и проблема реконфигурации пути. [15]
Заметки
- ^ неопубликованные результаты, принадлежащие Гэри и Джонсону, ср. Гэри и Джонсон (1979) : GT7
- ^ Уэно, Кадзитани и Гото (1988) ; Ли и Лю (1999)
- ^ Фомин и Вилланджер (2010)
- ^ Фомин и др. (2008) .
- ^ Разгон (2007) .
- ^ Чен и др. (2008) .
- ^ Уэно, Кадзитани & Гото (1988) .
- ^ Динур и Сафра 2005
- ^ а б Карп (1972)
- ^ Беккер и Гейгер (1996) . См. Также Bafna, Berman & Fujito (1999) для альтернативного алгоритма приближения с тем же коэффициентом приближения.
- ^ Erdős & Поза (1965) .
- ^ Silberschatz, Гальвин & Ганье (2008) .
- ^ Феста, Pardalos & Resende (2000) .
- ^ Kratsch, Стефан; Швейцер, Паскаль (2010). Каплан, Хаим (ред.). «Изоморфизм графов с ограниченным числом вершин обратной связи» . Теория алгоритмов - SWAT 2010 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 81–92. DOI : 10.1007 / 978-3-642-13731-0_9 . ISBN 978-3-642-13731-0.
- ^ «Алгоритмы и структуры данных | SpringerLink» (PDF) . DOI : 10.1007 / 978-3-030-24766-9.pdf # page = 370 . Цитировать журнал требует
|journal=
( помощь )
Рекомендации
Исследовательские статьи
- Бафна, Винит; Берман, Петр; Fujito, Тосихиро~d (1999), "Алгоритм 2-приближение для множества вершин задачи неориентированной обратной связи", SIAM журнал по дискретной математике , 12 (3): 289-297 (электронное), DOI : 10,1137 / S0895480196305124 , МР 1710236.
- Беккер, Энн; Бар-Иегуда, Реувен; Дэн Гейгер (2000), «Рандомизированные алгоритмы для задачи срезания цикла», Журнал исследований искусственного интеллекта , 12 : 219–234, arXiv : 1106.0225 , doi : 10.1613 / jair.638 , MR 1765590
- Беккер, Энн; Гейгер, Дэн (1996), «Оптимизация метода кондиционирования Перла и алгоритмов жадного приближения для задачи набора вершинной обратной связи», Искусственный интеллект , 83 (1): 167–188, CiteSeerX 10.1.1.25.1442 , doi : 10.1016 / 0004-3702 (95) 00004-6
- Цао, Исинь; Чен, Цзианэр; Лю, Ян (2010), "О множестве вершин обратной связи: новая мера и новые структуры", в Kaplan, Haim (ed.), Proc. 12-й скандинавский симпозиум и семинары по теории алгоритмов (SWAT 2010), Берген, Норвегия, 21-23 июня 2010 г. , лекции по информатике, 6139 , стр. 93–104, arXiv : 1004.1672 , Bibcode : 2010LNCS.6139 ... 93C , DOI : 10.1007 / 978-3-642-13731-0_10 , ISBN 978-3-642-13730-3
- Чен, Цзианэр; Фомин, Федор В .; Лю, Ян; Лу, Сунцзянь; Villanger, Yngve (2008), "Улучшенные алгоритмы для набора вершин обратных задач", журнал компьютерных и системных наук , 74 (7): 1188-1198, DOI : 10.1016 / j.jcss.2008.05.002 , MR 2454063
- Чен, Цзианэр; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), "Алгоритм с фиксированными параметрами для задачи о множестве вершин с направленной обратной связью", Журнал ACM , 55 (5), ст. 21, DOI : 10,1145 / 1411509,1411511 , МР 2456546
- Динур, Ирит ; Сафра, Самуэль (2005), "О жесткости аппроксимирующих минимальной вершины крышки" (PDF) , Анналы математики , второй серии, 162 (1): 439-485, DOI : 10.4007 / annals.2005.162.439 , MR 2178966
- Эрдеш, Пол ; Позы, Лайош (1965), "О независимых схемах содержится в графе" (PDF) , Canadian Journal математики , 17 : 347-352, DOI : 10,4153 / CJM-1965-035-8
- Фомин, Федор В .; Гасперс, Серж; Пяткин, Артем; Разгон, Игорь (2008), «О задаче с минимальным набором вершин обратной связи: алгоритмы точного и перечисления», Algorithmica , 52 (2): 293–307, CiteSeerX 10.1.1.722.8913 , doi : 10.1007 / s00453-007-9152 -0
- Фомин, Федор В .; Вилланджер, Ингве (2010), "Нахождение индуцированных подграфов с помощью минимальных триангуляций", Proc. 27-й Международный симпозиум по теоретическим аспектам информатики (STACS 2010) , Международные слушания по информатике Лейбница (LIPIcs), 5 , стр. 383–394, doi : 10.4230 / LIPIcs.STACS.2010.2470
- Карп, Ричард М. (1972), "Сводимость среди комбинаторных проблем", Proc. Симпозиум по сложности компьютерных вычислений, IBM Thomas J. Watson Res. Center, Yorktown Heights, Нью-Йорк , Нью-Йорк: Пленум, стр. 85–103.
- Ли, Деминг; Лю, Yanpei (1999), "Полиномиальный алгоритм для нахождения минимальной обратной связи множества вершин 3-регулярного простого графа", Acta Mathematica Scientia , 19 (4): 375-381, DOI : 10.1016 / s0252-9602 (17) 30520-9 , Руководство по ремонту 1735603
- Разгон, И. (2007), «Вычисление минимальной направленной вершины обратной связи, установленной в O * (1.9977 n )», на итальянском языке, Джузеппе Ф .; Моджи, Эухенио; Лаура, Луиджи (ред.), Труды 10-й Итальянской конференции по теоретической информатике (PDF) , World Scientific, стр. 70–81
- Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), "О неразрывной задаче о независимом множестве и задаче о множестве обратной связи для графов, степень вершины которых не превышает трех", Дискретная математика , 72 (1–3): 355–360, doi : 10.1016 / 0012- 365X (88) 90226-9 , Руководство по ремонту 0975556
Учебники и обзорные статьи
- Festa, P .; Пардалос, PM; Resende, MGC (2000), "Задачи о множестве обратной связи", Du, D.-Z .; Пардалос П.М. (ред.), Справочник по комбинаторной оптимизации, Дополнение, т. A (PDF) , Kluwer Academic Publishers, стр. 209–259.
- Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP- полноты, WH Freeman, A1.1: GT7, p. 191 , ISBN 978-0-7167-1045-5
- Зильбершац, Авраам; Гэлвин, Питер Баер; Гань, Грег (2008), Концепции операционных систем (8-е изд.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5