В теории графов , с независимым набором , стабильным набором , кокликой или anticlique представляет собой набор вершин в графе , никакие два из которых не являются смежными. То есть это такой набор вершин, что для каждых двух вершин в нем нет ребра, соединяющего их. Эквивалентно, каждое ребро в графе имеет не более одной конечной точки . Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа.. Размер независимого множества - это количество содержащихся в нем вершин. Независимые множества также называются «внутренне устойчивыми множествами», из которых «стабильное множество» является сокращением. [1]
Максимальное независимое множество является независимым набор , который не является собственным подмножеством любого другого независимого множества.
Максимальное независимое множество является независимым набором максимально возможного размера для данного графа . Этот размер называется числом независимости от и обычно обозначается . [2] задачи оптимизации найти такой набор называется максимальное независимое множество проблем. Это сильно NP-трудная проблема. [3] Таким образом, маловероятно, что существует эффективный алгоритм для поиска максимального независимого набора графа.
Каждое максимальное независимое множество также является максимальным, но обратное утверждение не обязательно.
Свойства [ править ]
| Пары покрытие / упаковка-проблема | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||
Связь с другими параметрами графика [ править ]
Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа , поэтому эти два понятия дополняют друг друга. Фактически, достаточно большие графы без больших клик имеют большие независимые множества, и эта тема исследуется в теории Рамсея .
Множество является независимым тогда и только тогда, когда его дополнение является вершинным покрытием . [4] Следовательно, сумма размера наибольшего независимого множества и размера минимального вершинного покрытия равна количеству вершин в графе.
Раскраска вершин графа соответствует к перегородке его множества вершин в независимых подмножеств. Следовательно, минимальное количество цветов, необходимое для раскраски вершин, хроматическое число , по крайней мере, является частным от количества вершин в и независимого числа .
В двудольном графе без изолированных вершин количество вершин в максимальном независимом множестве равно количеству ребер в минимальном покрытии рёбер ; это теорема Кёнига .
Максимальный независимый набор [ править ]
Независимый набор, который не является собственным подмножеством другого независимого набора, называется максимальным . Такие наборы являются доминирующими . Каждый граф содержит не более 3 n / 3 максимальных независимых множеств [5], но во многих графах их гораздо меньше. Количество максимальных независимых множеств в графах циклов с n вершинами задается числами Перрина , а количество максимальных независимых множеств в графах путей с n вершинами дается последовательностью Падована . [6] Следовательно, оба числа пропорциональны степени 1,324718 ..., пластического числа .
Поиск независимых множеств [ править ]
В информатике изучается несколько вычислительных задач, связанных с независимыми множествами.
- В задаче о максимальном независимом множестве входом является неориентированный граф, а выходом - максимальное независимое множество в графе. Если имеется несколько максимальных независимых наборов, нужно вывести только один. Эту проблему иногда называют « упаковкой вершин ».
- В максимальном весе независимого множества проблем, вход неориентированный граф с весами на его вершины , а выход является независимым множеством с максимальным суммарным весом. Задача о максимальном независимом множестве - это частный случай, когда все веса равны единице.
- В задаче перечисления максимальных независимых множеств входом является неориентированный граф, а выходом - список всех его максимальных независимых множеств. Задача о максимальном независимом множестве может быть решена с использованием в качестве подпрограммы алгоритма для задачи о максимальном независимом множестве, поскольку максимальное независимое множество должно быть включено среди всех максимальных независимых множеств.
- В задаче решения о независимом множестве входом является неориентированный граф и число k , а выходом - логическое значение : истина, если граф содержит независимый набор размера k , и ложь в противном случае.
Первые три из этих проблем важны для практических приложений; проблема решения о независимом множестве не является, но необходима для применения теории NP-полноты к проблемам, связанным с независимыми множествами.
Максимальное количество независимых множеств и максимальное количество кликов [ править ]
Независимая Поставленная задача и проблема клики дополняет друг друг: клика в G является независимым множеством в дополнительном графе из G , и наоборот. Следовательно, многие результаты вычислений могут быть одинаково хорошо применены к любой задаче. Например, результаты, относящиеся к проблеме клики, имеют следующие следствия:
- Проблема независимого множества решений является NP-полной , и поэтому не считается, что существует эффективный алгоритм для ее решения.
- Задача о максимальном независимом множестве является NP-трудной, и ее также трудно аппроксимировать .
Несмотря на тесную взаимосвязь между максимальными кликами и максимальными независимыми наборами в произвольных графах, проблемы с независимыми наборами и кликами могут сильно отличаться, если они ограничены специальными классами графов. Например, для разреженных графов (графов, в которых количество ребер не более чем константа, умноженная на количество вершин в любом подграфе), максимальная клика имеет ограниченный размер и может быть найдена точно за линейное время; [7], однако, для тех же классов графов или даже для более ограниченного класса графов с ограниченной степенью нахождение максимального независимого множества является MAXSNP-полным , что означает, что для некоторой константы c (в зависимости от степени) это NP -жесткийнайти приблизительное решение, которое находится в пределах с от оптимума. [8]
Поиск максимальных независимых множеств [ править ]
Точные алгоритмы [ править ]
Задача о максимальном независимом множестве является NP-сложной. Однако его можно решить более эффективно, чем время O ( n 2 2 n ), которое может дать наивный алгоритм грубой силы, который исследует каждое подмножество вершин и проверяет, является ли это независимым набором.
По состоянию на 2017 год его можно решить за время O (1,1996 n ), используя полиномиальное пространство. [9] Если ограничиваться графами с максимальной степенью 3, она может быть решена за время O (1.0836 n ). [10]
Для многих классов графов набор, не зависящий от максимального веса, может быть найден за полиномиальное время. Известными примерами являются графы без клешней , [11] P 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]
Независимые множества в графах пересечения интервалов [ править ]
Граф интервалов представляет собой график , в котором узлы являются 1-мерные интервалы (например , интервалы времени) и существует ребро между двумя интервалами тогда и только тогда они пересекаются. Независимый набор в графе интервалов - это просто набор неперекрывающихся интервалов. Проблема поиска максимальных независимых множеств в интервальных графах изучалась, например, в контексте планирования заданий : для заданного набора заданий, которые должны быть выполнены на компьютере, найти максимальный набор заданий, которые могут быть выполнены без вмешательства друг с другом. Эта проблема может быть решена точно за полиномиальное время, используя составление расписания в самый ранний крайний срок .
Независимые множества в геометрических графах пересечений [ править ]
Геометрический граф пересечения - это граф, узлы которого являются геометрическими фигурами, и между двумя фигурами есть ребро, если они пересекаются. Независимый набор в геометрическом графе пересечений - это просто набор непересекающихся (непересекающихся) фигур. Проблема поиска максимальных независимых наборов в геометрических графах пересечений изучалась, например, в контексте автоматического размещения меток : для заданного набора местоположений на карте найдите максимальный набор непересекающихся прямоугольных меток около этих местоположений.
Нахождение максимального независимого множества в графах пересечений по-прежнему является NP-полным, но его легче аппроксимировать, чем общую задачу о максимальном независимом множестве. Недавний обзор можно найти во введении к Chan & Har-Peled (2012) .
Нахождение максимальных независимых множеств [ править ]
Задача поиска максимального независимого множества может быть решена за полиномиальное время с помощью тривиального жадного алгоритма . [20] Все максимальные независимые множества могут быть найдены за время O (3 n / 3 ) = O (1.4423 n ).
Программа для поиска максимального независимого множества [ править ]
| Имя | Лицензия | Язык API | Краткая информация |
|---|---|---|---|
| граф | GPL | C, Python, R, Рубин | точное решение. «Текущая реализация была перенесена на igraph из библиотеки Very Nauty Graph Library Китом Бриггсом и использует алгоритм из статьи С. Цукияма, М. Иде, Х. Ариёши и И. Ширавака. Новый алгоритм для генерации всех максимальных независимых множеств SIAM J Computing, 6: 505–517, 1977 ». |
| LightGraphs | Массачусетский технологический институт | Юлия | точное решение. Смотрите документацию для более подробной информации. |
| NetworkX | BSD | Python | приблизительное решение, см. подпрограмму maximum_independent_set |
| мисс | Открыть | Rust (двоичные файлы) | приблизительное решение путем случайной выборки максимального независимого пространства множества, см. дополнительную информацию на веб-странице |
Приложения [ править ]
Максимально независимое множество и двойственная ему задача о минимальном покрытии вершин участвует в доказательстве вычислительной сложности многих теоретических задач. [21] Они также служат полезными моделями для реальных задач оптимизации, например, минимальный независимый набор является полезной моделью для обнаружения стабильных генетических компонентов для разработки инженерных генетических систем . [22]
См. Также [ править ]
- Независимый набор ребер - это набор ребер, у которых нет двух общих вершин. Обычно это называется сопоставлением .
- Раскраска вершин является разбиением множества вершин в независимые множества.
Заметки [ править ]
- ^ Коршунов (1974)
- ^ Godsil & Royle (2001) , стр. 3.
- ^ Garey, MR; Джонсон, Д.С. (1978-07-01). " " Сильные результаты NP-полноты: мотивация, примеры и последствия» . Журнал ACM . 25 (3): 499-508. DOI : 10,1145 / 322077,322090 . ISSN 0004-5411 .
- ^ ДОКАЗАТЕЛЬСТВО: Множество V вершин является независимым множеством IFF каждое ребро в графе смежно не более чем с одним элементом V IFF каждое ребро в графе смежно по крайней мере с одним элементом, не входящим в V IFF, дополнение к V является крышка вершины.
- Перейти ↑ Moon & Moser (1965) .
- ^ Furedi (1987) .
- ^ Chiba & Nishizeki (1985) .
- ^ Berman & Fujito (1995) .
- ↑ Сяо и Нагамочи (2017)
- ^ Сяо и Нагамочи (2013)
- ^ Минти (1980) , Sbihi (1980) , Накамура & Тамура (2001) , Фаэнца, Oriolo & Стауффер (2014) , Нобили & Сассано (2015)
- ^ Локштанов, Vatshelle & Villanger (2014)
- ^ Grötschel, Ловас & Шриджвер (1988)
- ↑ Франк (1976)
- ↑ Тарьян (1985)
- ^ Базган, Кристина ; Эскофье, Бруно; Paschos, Vangelis Th. (2005). «Полнота в классах стандартной и дифференциальной аппроксимации: Poly- (D) APX- и (D) PTAS-полнота» . Теоретическая информатика . 339 (2–3): 272–292. DOI : 10.1016 / j.tcs.2005.03.007 .
- ^ Бейкер (1994) ; Grohe (2003) .
- ^ Halldórsson & Radhakrishnan (1997) .
- ^ Хлебик, Мирослав; Хлебикова, Янка (2003). «Аппроксимация трудностей для малых вхождений NP-трудных задач». Материалы 5-й Международной конференции по алгоритмам и сложности . Конспект лекций по информатике. 2653 : 152–164. DOI : 10.1007 / 3-540-44849-7_21 . ISBN 978-3-540-40176-6.
- ^ Лубы (1986) .
- ^ Скиена, Стивен С. (2012). Руководство по разработке алгоритмов . Springer. ISBN 978-1-84800-069-8. OCLC 820425142 .
- ^ Хоссейн, Аян; Лопес, Эриберто; Хальпер, Шон М .; Cetnar, Daniel P .; Рейс, Александр С .; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13.07.2020). «Автоматизированное проектирование тысяч неповторяющихся частей для разработки стабильных генетических систем» . Природная биотехнология : 1–10. DOI : 10.1038 / s41587-020-0584-2 . ISSN 1546-1696 . PMID 32661437 . S2CID 220506228 .
Ссылки [ править ]
- Бейкер, Brenda S. (1994), "Приближенные алгоритмы для NP-полных задач на плоских графах", Журнал ACM , 41 (1): 153-180, DOI : 10,1145 / 174644,174650 , S2CID 9706753.
- Берман, Петр; Fujito, Toshihiro (1995), "Об аппроксимационных свойствах проблемы независимых множеств для графов степени 3", Практикум по алгоритмам и структурам данных , Lecture Notes in Computer Science, 955 , Springer-Verlag , стр. 449–460, doi : 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
- Буржуа, Николя; Эскофье, Бруно; Paschos, Vangelis Th .; van Rooij, Johan MM (2010), «Метод снизу вверх и быстрые алгоритмы для МАКСИМАЛЬНОГО НЕЗАВИСИМОГО набора», теория алгоритмов - SWAT 2010 , Lecture Notes in Computer Science, 6139 , Berlin: Springer, pp. 62–73, Bibcode : 2010LNCS.6139 ... 62В , DOI : 10.1007 / 978-3-642-13731-0_7 , ISBN 978-3-642-13730-3, MR 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.
- Chiba, N .; Nishizeki, Т. (1985), "Arboricity и алгоритмы подграф листинга", SIAM журнал по вычислениям , 14 (1): 210-223, DOI : 10,1137 / 0214017.
- Erlebach, T .; Jansen, K .; Зайдель, Э. (2005), «Схемы полиномиального приближения для геометрических графов пересечений», SIAM Journal on Computing , 34 (6): 1302, doi : 10,1137 / s0097539702402676.
- Faenza, Y .; Ориоло, G .; Stauffer, G. (2014), "Решение Weighted Стабильная Поставленная задача в Кло-Free графах", Журнал ACM , 61 (4): 1-41, DOI : 10,1145 / 2629600 , S2CID 1995056.
- Фомин, Федор В .; Грандони, Фабрицио; Kratsch, Дитер (2009), "Мера и захват подход к анализу точных алгоритмов", Журнал ACM , 56 (5): 1-32, DOI : 10,1145 / 1552285,1552286 , S2CID 1186651 , в статье нет. 25CS1 maint: postscript (link).
- Франк, Андрас (1976), "Некоторые полиномиальные алгоритмы для определенных графов и гиперграфов", Congressus Numerantium , XV : 211–226.
- Фуредите, З. (1987), "Число максимальных независимых множеств в связных графах", журнал теории графов , 11 (4): 463-470, DOI : 10.1002 / jgt.3190110403.
- Годсил, Крис ; Ройл, Гордон (2001), алгебраическая теория графов , Нью-Йорк: Спрингер , ISBN 978-0-387-95220-8.
- Grohe, Martin (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math / 0001128 , doi : 10.1007 / s00493-003-0037-9 , S2CID 11751235.
- Grötschel, M .; Ловас, Л .; Schrijver, A. (1988), «9.4 Раскраска идеальных графов», геометрические алгоритмы и комбинаторная оптимизация , алгоритмы и комбинаторика, 2 , Springer-Verlag , стр. 296–298, ISBN 978-0-387-13624-0.
- Halldórsson, MM; Радхакришнан, Дж. (1997), «Жадность - это хорошо: аппроксимация независимых множеств в разреженных графах и графах с ограниченной степенью», Algorithmica , 18 (1): 145–163, CiteSeerX 10.1.1.145.4523 , doi : 10.1007 / BF02523693 , S2CID 4661668.
- Коршунов, AD (1974), "Коэффициент внутренней стабильности", Кибернетика (на украинском языке ), 10 (1): 17-28, DOI : 10.1007 / BF01069014 , S2CID 120343511.
- Локштанов, Д .; Vatshelle, M .; Вилланджер, Ю. (2014), «Независимые множества в P 5 -свободных графах за полиномиальное время», SODA (симпозиум по дискретным алгоритмам) : 570–581.
- Лубы, Майкл (1986), "Простой параллельный алгоритм для максимального независимого множества проблем", SIAM журнал по вычислениям , 15 (4): 1036-1053, CiteSeerX 10.1.1.225.5475 , DOI : 10,1137 / 0215074 , MR 0861369.
- Минти, GJ (1980), "О максимальных независимых наборах вершин в графах без когтей", Журнал комбинаторной теории, серия B , 28 (3): 284–304, DOI : 10.1016 / 0095-8956 (80) 90074- Икс.
- Луна, JW; Мозер, Лео (1965), «О кликах в графах», Израильский журнал математики , 3 (1): 23–28, DOI : 10.1007 / BF02760024 , MR 0182577 , S2CID 9855414.
- Накамура, Д .; Тамура, А. (2001), «Пересмотр алгоритма Минти для поиска стабильного множества с максимальным весом в графе без когтей», Журнал Общества исследования операций, Япония , 44 : 194–204, doi : 10.15807 / jorsj.44.194.
- Nobili, P .; Сассано, А. (2015), Алгоритм O (n ^ 2 log n) для задачи взвешенного стабильного множества в графах без когтей , arXiv : 1501.05775 , Bibcode : 2015arXiv150105775N
- Robson, JM (1986), "Алгоритмы для максимальных независимых множеств", журнал алгоритмов , 7 (3): 425-440, DOI : 10,1016 / 0196-6774 (86) 90032-5.
- Sbihi, Наджиб (1980), "Algorithme де отборный d'ООН стабильного де cardinalité максимум данс ООН Graphe без étoile", Дискретная математика (на французском языке), 29 (1): 53-76, DOI : 10.1016 / 0012-365X (90 ) 90287-R , Руководство по эксплуатации 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.
- Тарьян, RE (1985), "Разложение по клике сепараторов", дискретная математика , 55 (2): 221-232, DOI : 10.1016 / 0012-365x (85) 90051-2.
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. "Максимальное независимое множество вершин" . MathWorld .
- Сложные тесты для максимальной клики, максимального независимого набора, минимального покрытия вершин и раскраски вершин
- Независимый набор и вершинное покрытие , Ханан Аяд.
