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

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

Определение

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

(неориентированный или направленный). ПРИМЕР: граф

G=(V,E)

и положительное целое число

k

.

ВОПРОС: Есть ли подмножество

X\subseteq V

с

|X|\leq k

такая, что когда все вершины

X

и их соседние ребра удаляются из

G

, остаток без цикла ?

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

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, ранг цепи легко вычислить: $|E|-|V|+|C|$ , где C — множество компонент связности графа. Проблема поиска наименьшего набора ребер обратной связи эквивалентна поиску остовного леса , что можно сделать за полиномиальное время .
Аналогичным понятием в ориентированном графе является набор дуг обратной связи (FAS) — набор направленных дуг, удаление которых делает граф ацикличным. Поиск наименьшего FAS является NP-трудной задачей. ^[9]

Приложения

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

Примечания

^ неопубликованные результаты Гэри и Джонсона, ср. Гэри и Джонсон (1979) : GT7
^ Уэно, Кадзитани и Гото (1988) ; Ли и Лю (1999)
^ Фомин и Вилланджер (2010)
^ Fomin et al. (2008) .
^ Razgon (2007) .
^ Чен и др. (2008) .
^ Уэно, Кадзитани и Гото (1988) .
^ Закусочная и медицина, 2005 г.
^ Перейти обратно: ^а ^б Карп (1972)
^ Беккер и Гейгер (1996) . См. также Bafna, Berman & Fujito (1999) об альтернативном алгоритме аппроксимации с тем же коэффициентом аппроксимации.
^ Гурусвами, Венкатесан; Манокаран, Раджекар; Рагхавендра, Прасад (2008). «Преодолеть случайный порядок сложно: неаппроксимируемость максимального ациклического подграфа» . 2008 г. 49-й ежегодный симпозиум IEEE по основам информатики . стр. 573–582. дои : 10.1109/FOCS.2008.51 . ISBN 978-0-7695-3436-7 . S2CID 8762205 .
^ Эвен, Г.; (Сеффи) Наор, Дж.; Шибер, Б.; Судан, М. (1998). «Аппроксимация множеств минимальной обратной связи и мультиразрезов в ориентированных графах» . Алгоритмика . 20 (2): 151–174. дои : 10.1007/PL00009191 . ISSN 0178-4617 . S2CID 2437790 .
^ Эрдеш и Поса (1965) .
^ Зильбершац, Гальвин и Ганье (2008) .
^ Феста, Пардалос и Ресенде (2000) .
^ Крач, Стефан; Швейцер, Паскаль (2010). «Изоморфизм графов с числом множества вершин с ограниченной обратной связью» . В Каплане, Хаим (ред.). Теория алгоритмов - Спецназ 2010 . Конспекты лекций по информатике. Том. 6139. Берлин, Гейдельберг: Springer. стр. 81–92. Бибкод : 2010LNCS.6139...81K . дои : 10.1007/978-3-642-13731-0_9 . ISBN 978-3-642-13731-0 .
^ Алгоритмы и структуры данных (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), «Оптимизация метода Перла кондиционирования и жадных алгоритмов аппроксимации для задачи множества вершин с обратной связью». Искусственный интеллект , 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), «Улучшенные алгоритмы для задач множества вершин с обратной связью», Журнал компьютерных и системных наук , 74 (7): 1188–1198, doi : 10.1016/j.jcss.2008.05.002 , MR 2454063
Чен, Цзянер; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированными параметрами для задачи множества вершин с направленной обратной связью», Журнал ACM , 55 (5), Ст. 21, doi : 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 , ISBN 978-0-7167-1045-5
Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (2008), Концепции операционной системы (8-е изд.), John Wiley & Sons. Инк, ISBN 978-0-470-12872-5

[1] неопубликованные результаты Гэри и Джонсона, ср. Гэри и Джонсон (1979) : GT7

[2] Уэно, Кадзитани и Гото (1988) ; Ли и Лю (1999)

[3] Фомин и Вилланджер (2010)

[FOOTNOTEFominGaspersPyatkinRazgon2008-4] Fomin et al. (2008) .

[FOOTNOTERazgon2007-5] Razgon (2007) .

[FOOTNOTEChenLiuLuO'Sullivan2008-6] Чен и др. (2008) .

[FOOTNOTEUenoKajitaniGotoh1988-7] Уэно, Кадзитани и Гото (1988) .

[8] Закусочная и медицина, 2005 г.

[k72-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 .

[FOOTNOTEErdősPósa1965-13] Эрдеш и Поса (1965) .

[FOOTNOTESilberschatzGalvinGagne2008-14] Зильбершац, Гальвин и Ганье (2008) .

[FOOTNOTEFestaPardalosResende2000-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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]