Набор вершин обратной связи

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

Определение

Проблема принятия решения FVS заключается в следующем:

ПРИМЕР: граф (неориентированный или направленный) и положительное целое число . ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

ВОПРОС: Существует ли подмножество с таким, что при удалении всех вершин и прилегающих к ним ребер из оставшаяся часть не содержит циклов ? ${\displaystyle X\subseteq V}$ ${\displaystyle |X|\leq k}$ ${\displaystyle X}$ ${\displaystyle G}$

Граф , который остается после удаления из, представляет собой индуцированный лес (соответственно индуцированный направленный ациклический граф в случае ориентированных графов ). Таким образом, нахождение минимального FVS в графе эквивалентно нахождению максимального индуцированного леса (соответственно, максимального индуцированного направленного ациклического графа в случае ориентированных графов ). ${\displaystyle G[V\setminus X]}$ ${\displaystyle X}$ ${\displaystyle G}$

NP-твердость

Карп (1972) показал, что задача минимального FVS для ориентированных графов является NP-полной . Задача остается NP-полной на ориентированных графах с максимальной входной и исходящей степенью два, а также на ориентированных планарных графах с максимальной входной и исходящей степенью три. ^[1]

Редукция Карпа также подразумевает NP-полноту задачи FVS на неориентированных графах, при этом проблема остается NP-трудной на графах максимальной степени четыре. Задача FVS может быть решена за полиномиальное время на графах максимальной степени не выше трех. ^[2]

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

Соответствующая задача NP-оптимизации по нахождению размера минимального набора вершин обратной связи может быть решена за время O (1,7347 ⁿ ), где n — количество вершин в графе. ^[3] Этот алгоритм фактически вычисляет максимальный индуцированный лес, и когда такой лес получается, его дополнением является минимальный набор вершин обратной связи. Число минимальных наборов вершин обратной связи в графе ограничено O (1,8638 ⁿ ). ^[4] Проблема множества вершин с направленной обратной связью все еще может быть решена за время O* (1,9977 ⁿ ), где n — количество вершин в заданном ориентированном графе. ^[5] Параметризованные версии направленных и ненаправленных задач являются решаемыми с фиксированными параметрами . ^[6]

В неориентированных графах максимальной степени три проблема множества вершин обратной связи может быть решена за полиномиальное время путем преобразования ее в экземпляр проблемы четности матроидов для линейных матроидов . ^[7]

Приближение

Ненаправленная задача — APX-полная . Это следует из следующих фактов.

• APX-полнота задачи вершинного покрытия ; ^[8]
• Существование аппроксимации, сохраняющей L-редукцию задачи вершинного покрытия к ней;
• Существующие алгоритмы аппроксимации с постоянным коэффициентом. ^[9]

Самый известный алгоритм аппроксимации неориентированных графов — в два раза. ^[10]

Напротив, направленную версию задачи приблизить гораздо труднее. Согласно гипотезе уникальных игр , недоказанному, но часто используемому предположению о вычислительной сложности , NP-трудно аппроксимировать задачу с точностью до любого постоянного множителя за полиномиальное время. Тот же результат по сложности был первоначально доказан для тесно связанной задачи о множестве дуг обратной связи , ^[11], но поскольку задача о множестве дуг обратной связи и проблема о множестве вершин обратной связи в ориентированных графах сводятся друг к другу с сохранением размеров решения, ^[12] он также верен для последнего.

Границы

Согласно теореме Эрдеша-Посы , размер минимального набора вершин обратной связи находится в пределах логарифмического коэффициента максимального количества вершинно-непересекающихся циклов в данном графе. ^[13]

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

• Вместо вершин можно рассматривать множество ребер обратной связи — множество ребер в неориентированном графе, удаление которых делает граф ацикличным. Размер наименьшего набора ребер обратной связи в графе называется рангом цепи графа. В отличие от числа FVS, ранг схемы легко вычислить: он равен , где C — множество компонент связности графа. Проблема поиска наименьшего набора ребер обратной связи эквивалентна поиску остовного леса , что можно сделать за полиномиальное время . ${\displaystyle |E|-|V|+|C|}$
• Аналогичным понятием в ориентированном графе является набор дуг обратной связи (FAS) — набор направленных дуг, удаление которых делает граф ацикличным. Поиск наименьшего FAS является NP-трудной задачей. ^[9]

Приложения

• В операционных системах наборы вершин обратной связи играют важную роль в изучении восстановления из тупиковой ситуации . В графе ожидания операционной системы каждый направленный цикл соответствует ситуации тупика. Чтобы разрешить все взаимоблокировки, необходимо прервать некоторые заблокированные процессы. Минимальный набор вершин обратной связи в этом графе соответствует минимальному количеству процессов, которые необходимо прервать. ^[14]
• Проблема набора вершин обратной связи находит применение в проектировании микросхем СБИС . ^[15]
• Другое приложение находится в теории сложности. Некоторые вычислительные задачи на графах в целом являются NP-сложными, но могут быть решены за полиномиальное время для графов с ограниченным числом FVS. Некоторыми примерами являются изоморфизм графов ^[16] и проблема реконфигурации путей. ^[17]

Примечания

1. неопубликованные результаты Гэри и Джонсона, ср. Гэри и Джонсон (1979): GT7
2. Уэно, Кадзитани и Гото (1988); Ли и Лю (1999)
3. Фомин и Вилланджер (2010)
4. Фомин и др. (2008).
5. Разгон (2007).
6. Чен и др. (2008).
7. Уэно, Кадзитани и Гото (1988).
8. Динур и Сафра 2005 г.
9. Карп (1972)
10. Беккер и Гейгер (1996). См. также Bafna, Berman & Fujito (1999) об альтернативном алгоритме аппроксимации с тем же коэффициентом аппроксимации.
11. Гурусвами, Венкатесан; Манокаран, Раджекар; Рагхавендра, Прасад (2008). «Преодолеть случайный порядок сложно: неаппроксимируемость максимального ациклического подграфа». 2008 г. 49-й ежегодный симпозиум IEEE по основам информатики . стр. 573–582. дои : 10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7. S2CID  8762205.
12. Эвен, Г.; (Сеффи) Наор, Дж.; Шибер, Б.; Судан, М. (1998). «Аппроксимация множеств минимальной обратной связи и мультиразрезов в ориентированных графах». Алгоритмика . 20 (2): 151–174. дои : 10.1007/PL00009191. ISSN  0178-4617. S2CID  2437790.
13. Эрдеш и Поса (1965).
14. Зильбершац, Гальвин и Ганье (2008).
15. Феста, Пардалос и Ресенде (2000).
16. Крач, Стефан; Швейцер, Паскаль (2010). «Изоморфизм графов с ограниченным числом наборов вершин обратной связи». В Каплане, Хаим (ред.). Теория алгоритмов - Спецназ 2010 . Конспекты лекций по информатике. Том. 6139. Берлин, Гейдельберг: Springer. стр. 81–92. Бибкод : 2010LNCS.6139...81K. дои : 10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.
17. Алгоритмы и структуры данных (PDF) . Конспекты лекций по информатике. Том. 11646. 2019. doi :10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID  198996919.

Рекомендации

Научные статьи

• Бафна, Винет; Берман, Петр; Фудзито, Тошихиро (1999), «Алгоритм с двумя приближениями для задачи множества вершин с ненаправленной обратной связью», SIAM Journal on Discrete Mathematics , 12 (3): 289–297 (электронный), doi : 10.1137/S0895480196305124, MR  1710236.
• Беккер, Энн; Бар-Иегуда, Реувен; Гейгер, Дэн (2000), «Рандомизированные алгоритмы для задачи о разрезе цикла», Журнал исследований искусственного интеллекта , 12 : 219–234, arXiv : 1106.0225 , doi : 10.1613/jair.638, MR  1765590, S2CID  10243677
• Беккер, Энн; Гейгер, Дэн (1996), «Оптимизация метода Перла кондиционирования и жадных алгоритмов аппроксимации для задачи множества вершин с обратной связью», Artificial Intelligence , 83 (1): 167–188, CiteSeerX  10.1.1.25.1442 , doi : 10.1016/0004-3702(95)00004-6
• Цао, Исинь; Чен, Цзянер; Лю, Ян (2010), «О множестве вершин обратной связи: новая мера и новые структуры», в книге Каплан, Хаим (ред.), 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
• Чен, Цзянер; Фомин Федор Владимирович; Лю, Ян; Лу, Сунцзянь; Вилланджер, Ингве (2008), «Улучшенные алгоритмы для задач множества вершин с обратной связью», Journal of Computer and System Sciences , 74 (7): 1188–1198, doi :10.1016/j.jcss.2008.05.002, MR  2454063
• Чен, Цзянер; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированным параметром для задачи множества вершин с направленной обратной связью», Журнал ACM , 55 (5), ст. 21, номер документа : 10.1145/1411509.1411511, MR  2456546, S2CID  1547510
• Динур, Ирит ; Сафра, Сэмюэл (2005), «О сложности аппроксимации минимального вершинного покрытия» (PDF) , Annals of Mathematics , Second Series, 162 (1): 439–485, doi : 10.4007/annals.2005.162.439, MR  2178966, заархивировано из оригинала (PDF) 20 сентября 2009 г. , получено 29 марта 2010 г.
• Эрдеш, Пол ; Поса, Лайош (1965), «О независимых схемах, содержащихся в графе» (PDF) , Canadian Journal of Mathematics , 17 : 347–352, doi : 10.4153/CJM-1965-035-8, S2CID  123981328
• Фомин Федор Владимирович; Гасперс, Серж; Пяткин, Артем; Разгон, Игорь (2008), «О проблеме минимального набора вершин обратной связи: точные и алгоритмы перечисления», Algorithmica , 52 (2): 293–307, CiteSeerX  10.1.1.722.8913 , doi : 10.1007/s00453-007-9152 -0, S2CID  731997
• Фомин Федор Владимирович; Виллангер, Ингве (2010), «Нахождение индуцированных подграфов с помощью минимальных триангуляций», Proc. 27-й Международный симпозиум по теоретическим аспектам информатики (STACS 2010) , Международные труды Лейбница по информатике (LIPIcs), том. 5, стр. 383–394, doi : 10.4230/LIPIcs.STACS.2010.2470, ISBN. 9783939897163, S2CID  436224
• Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Proc. Симпозиум по сложности компьютерных вычислений, IBM Thomas J. Watson Res. Центр, Йорктаун-Хайтс, Нью-Йорк , Нью-Йорк: Пленум, стр. 85–103.
• Ли, Деминг; Лю, Янпей (1999), «Полиномиальный алгоритм для поиска минимального набора вершин обратной связи 3-регулярного простого графа», Acta Mathematica Scientia , 19 (4): 375–381, doi :10.1016/s0252-9602(17) 30520-9, МР  1735603
• Разгон, И. (2007), «Вычисление минимального набора вершин направленной обратной связи в O * (1,9977 ⁿ )», на итальянском языке, Джузеппе Ф .; Моджи, Эудженио; Лаура, Луиджи (ред.), Труды 10-й итальянской конференции по теоретической информатике (PDF) , World Scientific, стр. 70–81.
• Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), «О проблеме неразделяющегося независимого множества и проблеме множества с обратной связью для графов, степень вершины которых не превышает трех», Discrete Mathematics , 72 (1–3): 355–360, doi : 10.1016/0012- 365Х(88)90226-9 , МР  0975556

Учебники и обзорные статьи

• Феста, П.; Пардалос, премьер-министр; Резенде, MGC (2000), «Проблемы набора обратной связи», Ду, Д.-З.; Пардалос, премьер-министр (ред.), Справочник по комбинаторной оптимизации, Приложение, том. A (PDF) , Kluwer Academic Publishers, стр. 209–259.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, A1.1: GT7, с. 191, ИСБН 978-0-7167-1045-5
• Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (2008), Концепции операционной системы (8-е изд.), John Wiley & Sons. Инк, ISBN 978-0-470-12872-5