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

Несвязанные вершины в графах

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

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

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

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

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

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

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

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

Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием . ^[4] Следовательно, сумма размера наибольшего независимого множества и размера минимального вершинного покрытия равна количеству вершин в графе. ${\displaystyle \alpha (G)}$ ${\displaystyle \beta (G)}$

Раскраска вершин графа соответствует разбиению его множества вершин на независимые подмножества. Следовательно, минимальное количество цветов, необходимое для раскраски вершин, хроматическое число , равно как минимум частному числа вершин в и независимого числа . ${\displaystyle G}$ ${\displaystyle \chi (G)}$ ${\displaystyle G}$ ${\displaystyle \alpha (G)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для многих классов графов максимальное независимое от веса множество может быть найдено за полиномиальное время. Известными примерами являются графы без клешней , ^[11] P ₅ -свободные графы ^[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 -когтей.
• Сайган ^[21] представил алгоритм с квазиполиномиальным временем , который для любого ε>0 достигает аппроксимации (d+ε)/3.

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

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

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

Нерешенная задача в информатике :

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

(еще нерешенные проблемы по информатике)

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

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

Приложения

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

Смотрите также

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

Примечания

1. Коршунов (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., цитируется в Curticapean, Radu; Делл, Хольгер; Фомин, Федор; Голдберг, Лесли Энн; Лапинскас, Джон (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. ОСЛК  820425142.
29. Хоссейн, Аяан; Лопес, Эриберто; Халпер, Шон М.; Цетнар, Дэниел П.; Рейс, Александр К.; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13 июля 2020 г.). «Автоматическое проектирование тысяч неповторяющихся деталей для разработки стабильных генетических систем». Природная биотехнология . 38 (12): 1466–1475. дои : 10.1038/s41587-020-0584-2. ISSN  1546-1696. PMID  32661437. S2CID  220506228.

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

• Бейкер, Бренда С. (1994), «Алгоритмы аппроксимации NP-полных задач на плоских графах», Журнал ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID  9706753.
• Берман, Петр; Фудзито, Тошихиро (1995), «Об аппроксимационных свойствах проблемы независимого множества для графов степени 3», Алгоритмы и структуры данных , Конспекты лекций по информатике, том. 955, Springer-Verlag , стр. 449–460, номер документа : 10.1007/3-540-60220-8_84, ISBN. 978-3-540-60220-0.
• Берман, Петр; Карпински, Марек (1999), «О некоторых более строгих результатах неаппроксимируемости», Автоматы, языки и программирование, 26-й международный коллоквиум, ICALP'99 Прага , Конспекты лекций по информатике , том. 1644, Прага: Springer-Verlag , стр. 200–209, doi : 10.1007/3-540-48523-6, ISBN. 978-3-540-66224-2, S2CID  23288736
• Буржуа, Николя; Эскофье, Бруно; Пашос, Вангелис Т.; ван Рой, Йохан М.М. (2010), «Метод снизу вверх и быстрые алгоритмы для МАКСИМАЛЬНОГО НЕЗАВИСИМОГО МНОЖЕСТВА», Теория алгоритмов - SWAT 2010 , Конспекты лекций по информатике, том. 6139, Берлин: Springer, стр. 62–73, Bibcode : 2010LNCS.6139...62B, doi : 10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, МР  2678485.
• Чан, Т.М. (2003), «Схемы аппроксимации полиномиального времени для упаковки и прокалывания толстых объектов», Journal of Algorithms , 46 (2): 178–189, CiteSeerX  10.1.1.21.5344 , doi : 10.1016/s0196-6774(02) )00294-8.
• Чан, ТМ ; Хар-Пелед, С. (2012), «Алгоритмы приближения для максимально независимого набора псевдодисков», Дискретная и вычислительная геометрия , 48 (2): 373, arXiv : 1103.1431 , CiteSeerX  10.1.1.219.2131 , doi : 10.1007/ s00454-012-9417-5 , S2CID  38183751.
• Чиба, Н.; Нишизеки, Т. (1985), «Древовидность и алгоритмы списка подграфов», SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017, S2CID  207051803.
• Эрлебах, Т.; Янсен, К.; Зайдель, Э. (2005), «Схемы аппроксимации полиномиальным временем для геометрических графов пересечений», SIAM Journal on Computing , 34 (6): 1302, doi : 10.1137/s0097539702402676.
• Фаэнца, Юрий; Ориоло, Джанпаоло; Стауффер, Готье (2014), «Решение проблемы взвешенного стабильного множества в графах без когтей», Журнал ACM , 61 (4): 1–41, doi : 10.1145/2629600, S2CID  1995056.
• Фомин Федор Владимирович; Грандони, Фабрицио; Крач, Дитер (2009), «Подход «измеряй и властвуй» для анализа точных алгоритмов», Журнал ACM , 56 (5): 1–32, doi : 10.1145/1552285.1552286, S2CID  1186651, статья №. 25,.
• Франк, Андраш (1976), «Некоторые полиномиальные алгоритмы для определенных графов и гиперграфов», Congressus Numerantium , XV : 211–226..
• Фюреди, Золтан (1987), «Число максимальных независимых множеств в связных графах», Journal of Graph Theory , 11 (4): 463–470, doi : 10.1002/jgt.3190110403.
• Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов , Нью-Йорк: Springer , ISBN 978-0-387-95220-8.
• Гроэ, Мартин (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math/0001128 , doi : 10.1007/s00493-003-0037-9 , S2CID  11751235.
• Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, МР  1261419.
• Халльдорссон, ММ; Радхакришнан, Дж. (1997), «Жадность — это хорошо: аппроксимация независимых множеств в разреженных графах и графах ограниченной степени», Algorithmica , 18 (1): 145–163, CiteSeerX  10.1.1.145.4523 , doi : 10.1007/BF02523693 , S2CID  4661668.
• Коршунов А.Д. (1974), «Коэффициент внутренней устойчивости», Кибернетика (на украинском языке), 10 (1): 17–28, doi :10.1007/BF01069014, S2CID  120343511.
• Локштанов Д.; Ватшелле, М.; Вилланджер, Ю. (2014), «Независимые множества в графах без P ₅ за полиномиальное время», SODA (Симпозиум по дискретным алгоритмам) : 570–581.
• Луби, Майкл (1986), «Простой параллельный алгоритм для задачи максимального независимого множества», SIAM Journal on Computing , 15 (4): 1036–1053, CiteSeerX  10.1.1.225.5475 , doi : 10.1137/0215074, MR  0861369.
• Минти, Г.Дж. (1980), «О максимальных независимых множествах вершин в графах без когтей», Журнал комбинаторной теории, серия B , 28 (3): 284–304, doi : 10.1016/0095-8956(80)90074- Икс.
• Мун, Дж.В.; Мозер, Лео (1965), «О кликах в графах», Израильский математический журнал , 3 (1): 23–28, doi : 10.1007/BF02760024, MR  0182577, S2CID  9855414.
• Накамура, Д.; Тамура, А. (2001), «Пересмотр алгоритма Минти для поиска максимального стабильного набора веса в графе без когтей», Журнал Общества исследования операций Японии , 44 (2): 194–204, doi : 10.15807/jorsj .44.194.
• Нобили, П.; Сассано, А. (2015), Алгоритм O (n ^ 2 log n) для задачи взвешенного устойчивого множества в графах без когтей , arXiv : 1501.05775 , Bibcode : 2015arXiv150105775N
• Робсон, Дж. М. (1986), «Алгоритмы для максимальных независимых множеств», Журнал алгоритмов , 7 (3): 425–440, doi : 10.1016/0196-6774(86)90032-5.
• Сбихи, Наджиба (1980), «Алгоритм исследования максимальной мощности в графе без звезды», Discrete Mathematics (на французском языке), 29 (1): 53–76, doi : 10.1016/0012-365X (90 )90287-Р , МР  0553650.
• Сяо, Мингю; Нагамоти, Хироши (2017), «Точные алгоритмы для максимально независимого множества», Information and Computation , 255 : 126–146, arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001, S2CID  1714739.
• Сяо, Мингю; Нагамоти, Хироши (2013), «Ограничение множеств и предотвращение узких мест: простой алгоритм максимального независимого множества в графах степени 3», Theoretical Computer Science , 469 : 92–104, doi : 10.1016/j.tcs.2012.09.022.
• Тарьян, Р.Э. (1985), «Разложение по кликовым сепараторам», Discrete Mathematics , 55 (2): 221–232, doi : 10.1016/0012-365x(85)90051-2.

Внешние ссылки

• Вайсштейн, Эрик В. «Максимальный независимый набор вершин». Математический мир .
• Сложные тесты для максимальной клики, максимального независимого набора, минимального покрытия вершин и раскраски вершин
• Независимый набор и вершинное покрытие, Ханан Аяд.