Jump to content

Независимое множество (теория графов)

(Перенаправлено из независимого набора вершин )
Девять синих вершин образуют максимальное независимое множество для обобщенного графа Петерсена GP(12,4).

В теории графов , независимое множество устойчивое множество , коклика или антиклика — это множество вершин графа . , никакие две из которых не являются смежными То есть это набор вершин такое, что для каждых двух вершин в , нет ребра, соединяющего их. Эквивалентно, каждое ребро графа имеет не более одной конечной точки. . Множество независимо тогда и только тогда, когда оно является кликой графа в ​​дополнении . Размер независимого множества — это количество содержащихся в нем вершин. Независимые множества также называют «внутренне стабильными множествами», сокращением которых является «стабильный набор». [1]

Максимальное независимое множество — это независимое множество, которое не является собственным подмножеством какого-либо другого независимого множества.

Максимальный независимый набор — это независимый набор максимально возможного размера для данного графа. . Эта величина называется независимости числом и обычно обозначается . [2] Оптимизационная задача поиска такого множества называется проблемой максимального независимого множества. Это сильно NP-трудная задача. [3] Таким образом, маловероятно, что существует эффективный алгоритм поиска максимального независимого множества графа.

Каждое максимальное независимое множество также является максимальным, но обратное импликация не обязательно имеет место.

Характеристики

[ редактировать ]

Связь с другими параметрами графика

[ редактировать ]

Множество является независимым тогда и только тогда, когда оно является кликой графа в ​​дополнении , поэтому эти две концепции дополняют друг друга. Фактически, достаточно большие графы без больших клик имеют большие независимые множества — тема, которая исследуется в теории Рамсея .

Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием . [4] Следовательно, сумма размеров наибольшего независимого множества и размер минимального вершинного покрытия равно числу вершин графа.

Вершинная раскраска графа соответствует разбиению его множества вершин на независимые подмножества. Отсюда минимальное количество цветов, необходимое для раскраски вершин, хроматическое число , является как минимум частным числом вершин в и независимое число .

В двудольном графе без изолированных вершин количество вершин в максимальном независимом множестве равно количеству ребер в минимальном покрытии ребер ; это теорема Кенига .

Максимально независимый набор

[ редактировать ]

Независимое множество, не являющееся собственным подмножеством другого независимого множества, называется максимальным . Такие множества являются доминирующими множествами . Каждый граф содержит не более 3 н /3 максимальные независимые множества, [5] но во многих графиках их гораздо меньше.Число максимальных независимых множеств в n- вершинных графах циклов определяется числами Перрена , а число максимальных независимых множеств в n -вершинных графах путей определяется последовательностью Падована . [6] Следовательно, оба числа пропорциональны степеням 1,324718..., коэффициенту пластичности .

Нахождение независимых множеств

[ редактировать ]

В информатике несколько вычислительных задач, изучалось связанных с независимыми множествами.

  • В задаче о максимальном независимом множестве входные данные представляют собой неориентированный граф, а выходные данные — максимальное независимое множество в графе. Если существует несколько максимальных независимых наборов, необходимо вывести только один. Эту проблему иногда называют « упаковкой вершин ».
  • В задаче о независимом множестве с максимальным весом входные данные представляют собой неориентированный граф с весами в вершинах, а выходные данные — независимый набор с максимальным общим весом. Задача о максимальном независимом множестве — это частный случай, когда все веса равны.
  • В задаче о перечислении максимальных независимых множеств входными данными является неориентированный граф, а выходными данными — список всех его максимальных независимых множеств. Задача о максимальном независимом множестве может быть решена с использованием в качестве подпрограммы алгоритма для задачи перечисления максимального независимого множества, поскольку максимальное независимое множество должно быть включено среди всех максимальных независимых множеств.
  • В задаче решения независимого набора входными данными является неориентированный граф и число k , а выходными данными является логическое значение : true, если граф содержит независимый набор размера k , и false в противном случае.

Первые три из этих проблем важны для практических приложений; проблема решения независимого множества не существует, но она необходима для применения теории NP-полноты к проблемам, связанным с независимыми множествами.

Максимальные независимые множества и максимальные клики

[ редактировать ]

Проблема независимого множества и проблема клики дополняют друг друга: клика в G является независимым множеством в графе дополнений G , и наоборот. Следовательно, многие результаты вычислений могут быть одинаково хорошо применены к любой задаче. Например, результаты, связанные с проблемой клики, имеют следующие следствия:

  • Задача решения независимого множества является NP-полной , и поэтому не считается, что существует эффективный алгоритм ее решения.
  • Задача о максимальном независимом множестве NP-трудна , и ее также трудно аппроксимировать .

Несмотря на тесную связь между максимальными кликами и максимальными независимыми множествами в произвольных графах, проблемы независимых множеств и клик могут сильно различаться, если ограничиваться специальными классами графов. Например, для разреженных графов (графов, в которых количество ребер не превышает константы, умноженной на количество вершин в любом подграфе), максимальная клика имеет ограниченный размер и может быть найдена точно за линейное время; [7] однако для тех же классов графов или даже для более ограниченного класса графов ограниченной степени нахождение максимального независимого множества является MAXSNP-полным , а это означает, что для некоторой константы c (в зависимости от степени) NP-трудно найти найти приближенное решение, которое находится в пределах c от оптимума. [8]

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

[ редактировать ]

Задача о максимальном независимом множестве NP-трудна. Однако ее можно решить более эффективно, чем O( n 2  2 н ) время, которое можно было бы получить с помощью простого алгоритма грубой силы , который исследует каждое подмножество вершин и проверяет, является ли оно независимым набором.

По состоянию на 2017 год ее можно решить за время O (1,1996 н ) с использованием полиномиального пространства. [9] Если ограничиться графами с максимальной степенью 3, ее можно решить за время O(1,0836 н ). [10]

Для многих классов графов максимальное независимое от веса множество может быть найдено за полиномиальное время. Известные примеры — графы без когтей , [11] П 5 -свободные графики [12] и идеальные графики . [13] Для хордальных графов максимальное независимое от веса множество можно найти за линейное время. [14]

Модульная декомпозиция — хороший инструмент для решения задачи о независимом множестве максимального веса; Алгоритм линейного времени на кографах является основным примером этого. Еще одним важным инструментом являются разделители кликов , описанные Тарьяном. [15]

Теорема Кенига подразумевает, что в двудольном графе максимальное независимое множество может быть найдено за полиномиальное время с использованием алгоритма двудольного сопоставления.

Алгоритмы аппроксимации

[ редактировать ]

В общем, задача о максимальном независимом множестве не может быть аппроксимирована постоянным коэффициентом за полиномиальное время (если только P = NP). Фактически, Max Independent Set в целом является Poly-APX-полным , что означает, что он так же сложен, как и любая задача, которую можно аппроксимировать полиномиальным коэффициентом. [16] Однако существуют эффективные алгоритмы аппроксимации для ограниченных классов графов.

В планарных графах

[ редактировать ]

В плоских графах максимальный независимый набор может быть аппроксимирован с точностью до любого коэффициента аппроксимации c <1 за полиномиальное время; подобные схемы аппроксимации за полиномиальное время существуют в любом семействе графов, замкнутых относительно принятия миноров . [17]

В графах ограниченной степени

[ редактировать ]

В графах ограниченной степени известны эффективные алгоритмы аппроксимации с коэффициентами аппроксимации , постоянными при фиксированном значении максимальной степени; например, жадный алгоритм , который формирует максимальное независимое множество, выбирая на каждом шаге вершину минимальной степени в графе и удаляя ее соседей, достигает коэффициента аппроксимации (Δ+2)/3 на графах с максимальной степенью Δ. [18] Границы жесткости аппроксимации для таких случаев были доказаны Берманом и Карпински (1999) . Действительно, даже Max Independent Set на 3-регулярных графах с 3-реберной раскраской является APX-полным . [19]

В графах пересечения интервалов

[ редактировать ]

Граф интервалов — это граф, узлами которого являются одномерные интервалы (например, временные интервалы), и между двумя интервалами существует ребро тогда и только тогда, когда они пересекаются. Независимый набор в графе интервалов — это просто набор непересекающихся интервалов. Проблема поиска максимальных независимых наборов в интервальных графах изучалась, например, в контексте планирования заданий : задан набор заданий, который необходимо выполнить на компьютере, найти максимальный набор заданий, которые можно выполнить, не мешая друг с другом. Эту проблему можно решить точно за полиномиальное время, используя планирование с самым ранним сроком выполнения .

В графах геометрических пересечений

[ редактировать ]

Граф геометрических пересечений — это граф, в котором узлами являются геометрические фигуры, а между двумя фигурами существует ребро тогда и только тогда, когда они пересекаются. Независимый набор в графе геометрических пересечений — это просто набор непересекающихся (непересекающихся) фигур. Проблема поиска максимальных независимых множеств в графах геометрических пересечений изучалась, например, в контексте автоматического размещения меток : по заданному набору мест на карте найдите максимальный набор непересекающихся прямоугольных меток рядом с этими местоположениями.

Поиск максимального независимого множества в графах пересечений по-прежнему является NP-полным, но его легче аппроксимировать, чем общую задачу о максимальном независимом множестве. Результаты недавнего исследования можно найти во введении Chan & Har-Peled (2012) .

В графах без d-когтей

[ редактировать ]

D -клешня в графе — это набор из d +1 вершин, одна из которых («центр») соединена с другими d вершинами, но остальные d вершины не связаны друг с другом. Граф d - без когтей — это граф, в котором нет подграфа d -когтей. Рассмотрим алгоритм, который начинается с пустого набора и постепенно добавляет к нему произвольную вершину, пока она не смежна ни с одной существующей вершиной. В графах без d -когтей каждая добавленная вершина делает недействительным не более d -1 вершины из максимального независимого набора; следовательно, этот тривиальный алгоритм достигает алгоритма ( d -1)-аппроксимации для максимального независимого множества. На самом деле можно получить гораздо лучшие коэффициенты аппроксимации:

  • Нойвонер [20] представил алгоритм с полиномиальным временем, который для любой константы ε>0 находит ( d /2-1/63,700,992+ε)-аппроксимацию для максимального независимого от веса множества в графе без d -когтей.
  • Cygan [21] представил алгоритм с квазиполиномиальным временем , который для любого ε>0 достигает аппроксимации (d+ε)/3.

Нахождение максимальных независимых множеств

[ редактировать ]

Задача нахождения максимального независимого множества может быть решена за полиномиальное время с помощью тривиального параллельного жадного алгоритма . [22] Все максимальные независимые множества можно найти за время O(3 н /3 ) = О(1,4423 н ).

Подсчет независимых наборов

[ редактировать ]
Нерешенная задача в информатике :
Существует ли полностью полиномиальный алгоритм аппроксимации количества независимых множеств в двудольных графах?

Задача подсчета #IS спрашивает, сколько независимых множеств в неориентированном графе он содержит. Эта задача трудноразрешима, а именно, она ♯P -полна уже на графах максимальной степени три. [23] Далее известно, что, если предположить, что NP отличается от RP , проблема не может быть легко аппроксимирована в том смысле, что она не имеет полностью полиномиальной схемы аппроксимации с рандомизацией (FPRAS), даже на графах с максимальной степенью шесть; [24] однако у него есть схема аппроксимации полностью полиномиального времени (FPTAS) в случае, когда максимальная степень равна пяти. [25] Задача #BIS о подсчете независимых множеств на двудольных графах также является ♯P -полной, уже на графах максимальной степени три. [26] Неизвестно, признает ли #BIS FPRAS. [27]

вопрос о подсчете максимальных независимых множеств Изучен также .

Приложения

[ редактировать ]

Максимальный независимый набор и его дополнение, задача минимального вершинного покрытия , используются для доказательства вычислительной сложности многих теоретических задач. [28] Они также служат полезными моделями для решения реальных задач оптимизации, например, максимальное независимое множество является полезной моделью для обнаружения стабильных генетических компонентов для проектирования инженерных генетических систем . [29]

См. также

[ редактировать ]
  • Независимый набор ребер — это набор ребер, среди которых нет двух общих вершин. Обычно это называется сопоставлением .
  • Раскраска вершин — это разбиение множества вершин на независимые множества.

Примечания

[ редактировать ]
  1. ^ Korshunov (1974)
  2. ^ Годсил и Ройл (2001) , с. 3.
  3. ^ Гэри, MR; Джонсон, DS (1 июля 1978 г.). « Сильные» результаты NP-полноты: мотивация, примеры и последствия» . Журнал АКМ . 25 (3): 499–508. дои : 10.1145/322077.322090 . ISSN   0004-5411 . S2CID   18371269 .
  4. ^ Доказательство: множество вершин V является независимым множеством. тогда и только тогда, когда каждое ребро в графе смежно не более чем с одним элементом V, тогда и только тогда, когда каждое ребро в графе смежно хотя бы с одним элементом, не принадлежащим V, тогда и только тогда, когда дополнение к V является вершиной крышка.
  5. ^ Мун и Мозер (1965) .
  6. ^ Фюреди (1987) .
  7. ^ Чиба и Нисидзеки (1985) .
  8. ^ Берман и Фудзито (1995) .
  9. ^ Сяо и Нагамоти (2017)
  10. ^ Сяо и Нагамоти (2013)
  11. ^ Минти (1980) , Сбихи (1980) , Накамура и Тамура (2001) , Фаэнца, Ориоло и Стауффер (2014) , Нобили и Сассано (2015)
  12. ^ Локштанов, Ватшелле и Вилланджер (2014)
  13. ^ Гретшель, Ловас и Шрийвер (1993 , Глава 9: Стабильные множества в графах)
  14. ^ Фрэнк (1976)
  15. ^ Тарьян (1985)
  16. ^ Базган, Кристина ; Эскофье, Бруно; Пашос, Вангелис Т. (2005). «Полнота в стандартных и дифференциальных классах аппроксимации: поли-(D)APX- и (D)PTAS-полнота» . Теоретическая информатика . 339 (2–3): 272–292. дои : 10.1016/j.tcs.2005.03.007 . S2CID   1418848 .
  17. ^ Бейкер (1994) ; Гроэ (2003) .
  18. ^ Халлдорссон и Радхакришнан (1997) .
  19. ^ Хлебик, Мирослав; Хлебикова, Янка (2003). «Твердость аппроксимации для небольших случаев возникновения NP-сложных задач» . Материалы 5-й Международной конференции по алгоритмам и сложности . Конспекты лекций по информатике. Том. 2653. стр. 152–164. дои : 10.1007/3-540-44849-7_21 . ISBN  978-3-540-40176-6 .
  20. ^ Нойвонер, Майке (07.06.2021), Улучшенный алгоритм аппроксимации для задачи независимого множества о максимальном весе в свободных графах с d-когтями , arXiv : 2106.03545
  21. ^ Циган, Марек (октябрь 2013 г.). «Улучшенное приближение для трехмерного сопоставления посредством локального поиска с ограниченной шириной пути» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 509–518. arXiv : 1304.1424 . дои : 10.1109/FOCS.2013.61 . ISBN  978-0-7695-5135-7 . S2CID   14160646 .
  22. ^ Луби (1986) .
  23. ^ Дайер, Мартин; Гринхилл, Кэтрин (1 апреля 2000 г.). «О цепях Маркова для независимых множеств» . Журнал алгоритмов . 35 (1): 17–49. дои : 10.1006/jagm.1999.1071 . ISSN   0196-6774 .
  24. ^ Хитрый, Аллан (2010). «Вычислительный переход на пороге уникальности» . 2010 51-й ежегодный симпозиум IEEE по основам информатики . стр. 287–296. дои : 10.1109/FOCS.2010.34 . ISBN  978-1-4244-8525-3 . S2CID   901126 .
  25. ^ Безакова, Ивона; Галанис, Андреас; Голдберг, Лесли Энн; Го, Хэн; Штефанкович, Даниэль (2019). «Аппроксимация посредством затухания корреляции при невозможности сильного пространственного смешивания» . SIAM Journal по вычислительной технике . 48 (2): 279–349. arXiv : 1510.09193 . дои : 10.1137/16M1083906 . ISSN   0097-5397 . S2CID   131975798 .
  26. ^ Ся, Минджи; Чжан, Пэн; Чжао, Вэньбо (24 сентября 2007 г.). «Вычислительная сложность задач счета на 3-регулярных планарных графах» . Теоретическая информатика . Теория и приложения моделей вычислений. 384 (1): 111–125. дои : 10.1016/j.tcs.2007.05.023 . ISSN   0304-3975 . , цитируется в Куртикапин, Раду; Делл, Хольгер; Фомин, Федор; Голдберг, Лесли Энн; Лапинскас, Джон (01 октября 2019 г.). «Перспектива #BIS с фиксированными параметрами» . Алгоритмика . 81 (10): 3844–3864. дои : 10.1007/s00453-019-00606-4 . hdl : 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN   1432-0541 . S2CID   3626662 .
  27. ^ Кэннон, Сара; Перкинс, Уилл (2020). Чавла, Шучи (ред.). Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. arXiv : 1906.01666 . дои : 10.1137/1.9781611975994.88 . ISBN  978-1-61197-599-4 . S2CID   174799567 .
  28. ^ Скиена, Стивен С. (2012). Руководство по проектированию алгоритма . Спрингер. ISBN  978-1-84800-069-8 . OCLC   820425142 .
  29. ^ Хоссейн, Аяан; Лопес, Эриберто; Халпер, Шон М.; Цетнар, Дэниел П.; Рейс, Александр К.; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13 июля 2020 г.). «Автоматизированное проектирование тысяч неповторяющихся деталей для создания стабильных генетических систем» . Природная биотехнология . 38 (12): 1466–1475. дои : 10.1038/s41587-020-0584-2 . ISSN   1546-1696 . ПМИД   32661437 . S2CID   220506228 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a5a0aa6b4990218d8098c1eb64b0abef__1716941220
URL1:https://arc.ask3.ru/arc/aa/a5/ef/a5a0aa6b4990218d8098c1eb64b0abef.html
Заголовок, (Title) документа по адресу, URL1:
Independent set (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)