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

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

Девять синих вершин образуют максимальное независимое множество для обобщенного графа Петерсена 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)}$

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

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

Независимое множество, которое не является собственным подмножеством другого независимого множества, называется максимальным . Такие множества являются доминирующими множествами . Каждый граф содержит не более 3 ^{n /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 ⁿ ), которое дал бы наивный алгоритм грубой силы , который проверяет каждое подмножество вершин и является ли оно независимым множеством.

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

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

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

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

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

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

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

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

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

В графах ограниченной степени известны эффективные алгоритмы аппроксимации с коэффициентами аппроксимации , которые постоянны для фиксированного значения максимальной степени; например, жадный алгоритм , который формирует максимальный независимый набор, выбирая на каждом шаге вершину минимальной степени в графе и удаляя ее соседей, достигает коэффициента аппроксимации (Δ+2)/3 на графах с максимальной степенью Δ. ^[18] Границы сложности аппроксимации для таких случаев были доказаны в работе Бермана и Карпински (1999). Действительно, даже максимальный независимый набор на 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 ^{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. Garey, MR; Johnson, DS (1978-07-01). "Результаты "сильной" NP-полноты: мотивация, примеры и следствия". Journal of the ACM . 25 (3): 499–508. doi : 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). «Полнота в стандартных и дифференциальных классах аппроксимации: полнота Poly-(D)APX и (D)PTAS». Теоретическая информатика . 339 (2–3): 272–292. doi : 10.1016/j.tcs.2005.03.007 . S2CID  1418848.
17. Бейкер (1994); Гроэ (2003).
18. Халлдорссон и Радхакришнан (1997).
19. Chlebík, Miroslav; Chlebíková, Janka (2003). "Aproximation Hardness for Small Occurrence Instances of NP-Hard Problems". Труды 5-й Международной конференции по алгоритмам и сложности . Lecture Notes in Computer Science. Vol. 2653. pp. 152–164. doi :10.1007/3-540-44849-7_21. ISBN 978-3-540-40176-6.
20. Нойвонер, Майке (2021-06-07), Улучшенный алгоритм аппроксимации для задачи о максимальном весе независимого множества в графах без d-клешней , arXiv : 2106.03545
21. Cygan, Marek (октябрь 2013 г.). «Улучшенная аппроксимация для 3-мерного сопоставления с помощью локального поиска с ограниченной шириной пути». 54-й ежегодный симпозиум IEEE по основам компьютерной науки 2013 г. стр. 509–518. arXiv : 1304.1424 . doi :10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID  14160646.
22. Луби (1986).
23. Дайер, Мартин; Гринхилл, Кэтрин (2000-04-01). «О цепях Маркова для независимых множеств». Журнал алгоритмов . 35 (1): 17–49. doi :10.1006/jagm.1999.1071. ISSN  0196-6774.
24. Слай, Аллан (2010). «Вычислительный переход на пороге уникальности». 51-й ежегодный симпозиум IEEE по основам компьютерной науки 2010 г. стр. 287–296. doi :10.1109/FOCS.2010.34. ISBN 978-1-4244-8525-3. S2CID  901126.
25. Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). «Approximation via Correlation Decay When Strong Spatial Mixing Fails». SIAM Journal on Computing . 48 (2): 279–349. arXiv : 1510.09193 . doi : 10.1137/16M1083906. ISSN  0097-5397. S2CID  131975798.
26. Ся, Минцзи; Чжан, Пэн; Чжао, Вэньбо (2007-09-24). «Вычислительная сложность задач подсчета на 3-регулярных планарных графах». Теоретическая информатика . Теория и приложения моделей вычислений. 384 (1): 111–125. doi :10.1016/j.tcs.2007.05.023. ISSN  0304-3975., цитируется в Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01). "A Fixed-Parameter Perspective on #BIS". Algorithmica . 81 (10): 3844–3864. doi : 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 . doi :10.1137/1.9781611975994.88. ISBN 978-1-61197-599-4. S2CID  174799567.
28. Скиена, Стивен С. (2012). Руководство по разработке алгоритмов . Springer. ISBN 978-1-84800-069-8. OCLC  820425142.
29. Хоссейн, Аян; Лопес, Эриберто; Халпер, Шон М.; Цетнар, Дэниел П.; Рейс, Александр К.; Стрикленд, Девин; Клавинс, Эрик; Салис, Говард М. (2020-07-13). «Автоматизированное проектирование тысяч неповторяющихся частей для проектирования стабильных генетических систем». Nature Biotechnology . 38 (12): 1466–1475. doi :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, doi :10.1007/3-540-60220-8_84, ISBN 978-3-540-60220-0.
• Берман, Петр; Карпински, Марек (1999), «О некоторых более жестких результатах неаппроксимируемости», Автоматы, языки и программирование, 26-й Международный коллоквиум, ICALP'99 Прага , Lecture Notes in Computer Science , т. 1644, Прага: Springer-Verlag , стр. 200–209, doi :10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, S2CID  23288736
• Буржуа, Николя; Эскофье, Бруно; Пашос, Вангелис Т.; ван Рой, Йохан ММ (2010), "Метод снизу вверх и быстрые алгоритмы для MAX INDENENDENT SET", Теория алгоритмов - 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), «Схемы полиномиального времени аппроксимации для упаковки и прокалывания толстых объектов», Журнал алгоритмов , 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), «Число максимальных независимых множеств в связных графах», Журнал теории графов , 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-x.
• Мун, Дж. В.; Мозер, Лео (1965), «О кликах в графах», Israel Journal of Mathematics , 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), «Точные алгоритмы для максимального независимого множества», Информация и вычисления , 255 : 126–146, arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001, S2CID  1714739.
• Сяо, Минюй; Нагамочи, Хироши (2013), «Ограничение множеств и избежание случаев узких мест: простой алгоритм максимального независимого множества в графах степени 3», Теоретическая информатика , 469 : 92–104, doi : 10.1016/j.tcs.2012.09.022.
• Тарьян, Р. Э. (1985), «Разложение по разделителям клик», Дискретная математика , 55 (2): 221–232, doi : 10.1016/0012-365x(85)90051-2.

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

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