Независимое множество (теория графов) - Independent set (graph theory)
В теории графов , с независимым набором , стабильным набором , кокликой или anticlique представляет собой набор вершин в графе , никакие два из которых не являются смежными. То есть это такой набор вершин, что для каждых двух вершин в нем нет ребра, соединяющего их. Эквивалентно, каждое ребро в графе имеет не более одной конечной точки . Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа . Размер независимого множества - это количество содержащихся в нем вершин. Независимые множества также называются «внутренне устойчивыми множествами», из которых «стабильное множество» является сокращением.
Максимальное независимое множество является независимым набор , который не является собственным подмножеством любого другого независимого множества.
Максимальное независимое множество является независимым набором максимально возможного размера для данного графа . Этот размер называется числом независимости от и обычно обозначается . Задача оптимизации поиска такого множества называется задачей максимального независимого множества. Это сильно NP-трудная проблема. Таким образом, маловероятно, что существует эффективный алгоритм для поиска максимального независимого набора графа.
Каждое максимальное независимое множество также является максимальным, но обратное утверждение не обязательно.
Характеристики
Связь с другими параметрами графика
Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа , поэтому эти два понятия дополняют друг друга. Фактически, достаточно большие графы без больших клик имеют большие независимые множества, и эта тема исследуется в теории Рамсея .
Множество является независимым тогда и только тогда, когда его дополнение является вершинным покрытием . Следовательно, сумма размера наибольшего независимого множества и размера минимального вершинного покрытия равна количеству вершин в графе.
Раскраска вершин графа соответствует к перегородке его множества вершин в независимых подмножеств. Следовательно, минимальное количество цветов, необходимое для раскраски вершин, хроматическое число , по крайней мере, является частным от количества вершин в и независимого числа .
В двудольном графе без изолированных вершин количество вершин в максимальном независимом множестве равно количеству ребер в минимальном покрытии рёбер ; это теорема Кёнига .
Максимальный независимый набор
Независимый набор, который не является собственным подмножеством другого независимого набора, называется максимальным . Такие наборы являются доминирующими . Каждый граф содержит не более 3 n / 3 максимальных независимых множеств, но во многих графах их гораздо меньше. Количество максимальных независимых множеств в графах циклов с n вершинами задается числами Перрина , а количество максимальных независимых множеств в графах путей с n вершинами дается последовательностью Падована . Следовательно, оба числа пропорциональны степени 1,324718 ..., пластического числа .
Поиск независимых множеств
В информатике изучается несколько вычислительных задач, связанных с независимыми множествами.
- В задаче о максимальном независимом множестве входом является неориентированный граф, а выходом - максимальное независимое множество в графе. Если имеется несколько максимальных независимых наборов, нужно вывести только один. Эту проблему иногда называют « упаковкой вершин ».
- В максимальном весе независимого множества проблем, вход неориентированный граф с весами на его вершины , а выход является независимым множеством с максимальным суммарным весом. Задача о максимальном независимом множестве - это частный случай, когда все веса равны единице.
- В задаче перечисления максимальных независимых множеств входом является неориентированный граф, а выходом - список всех его максимальных независимых множеств. Задача о максимальном независимом множестве может быть решена с использованием в качестве подпрограммы алгоритма для задачи о максимальном независимом множестве, поскольку максимальное независимое множество должно быть включено среди всех максимальных независимых множеств.
- В задаче решения о независимом множестве входом является неориентированный граф и число k , а выходом - логическое значение : истина, если граф содержит независимый набор размера k , и ложь в противном случае.
Первые три из этих проблем важны для практических приложений; проблема решения о независимом множестве не является, но необходима для применения теории NP-полноты к проблемам, связанным с независимыми множествами.
Максимальные независимые множества и максимальные клики
Независимая Поставленная задача и проблема клики дополняет друг друг: клика в G является независимым множеством в дополнительном графе из G , и наоборот. Следовательно, многие результаты вычислений могут быть одинаково хорошо применены к любой задаче. Например, результаты, относящиеся к проблеме клики, имеют следующие следствия:
- Проблема независимого множества решений является NP-полной , и поэтому не считается, что существует эффективный алгоритм для ее решения.
- Задача о максимальном независимом множестве является NP-трудной, и ее также трудно аппроксимировать .
Несмотря на тесную взаимосвязь между максимальными кликами и максимальными независимыми наборами в произвольных графах, проблемы с независимыми наборами и кликами могут сильно отличаться, когда они ограничиваются специальными классами графов. Например, для разреженных графов (графов, в которых количество ребер не более чем на постоянную величину, умноженную на количество вершин в любом подграфе), максимальная клика имеет ограниченный размер и может быть найдена точно за линейное время; Однако, для одних и тех же классов графов, или даже для более узкого класса ограниченных графов степени, нахождение максимального независимого множества является MAXSNP-полной , это означает , что для некоторой константы с ( в зависимости от степени) является NP-трудной в найти приблизительное решение, которое укладывается в коэффициент c от оптимума.
Нахождение максимальных независимых множеств
Точные алгоритмы
Задача о максимальном независимом множестве является NP-сложной. Однако его можно решить более эффективно, чем время O ( n 2 2 n ), которое может дать наивный алгоритм грубой силы, который исследует каждое подмножество вершин и проверяет, является ли это независимым набором.
По состоянию на 2017 год его можно решить за время O (1,1996 n ), используя полиномиальное пространство. Если ограничиться графами с максимальной степенью 3, она может быть решена за время O (1.0836 n ).
Для многих классов графов набор, не зависящий от максимального веса, может быть найден за полиномиальное время. Известные примеры коготь свободной графика , P 5 -свободные графики и прекрасные графики . Для хордовых графиков набор, не зависящий от максимального веса, может быть найден за линейное время.
Модульная декомпозиция - хороший инструмент для решения задачи о максимальном независимом множестве веса; алгоритм линейного времени на кографах является основным примером этого. Еще один важный инструмент - разделители кликов, описанные Тарьяном.
Теорема Кёнига подразумевает, что в двудольном графе максимальное независимое множество может быть найдено за полиномиальное время с использованием алгоритма двудольного сопоставления.
Алгоритмы аппроксимации
В общем, задача о максимальном независимом множестве не может быть приближена к постоянному множителю за полиномиальное время (если P = NP). Фактически, Max Independent Set в целом является Poly-APX-полным , что означает, что он так же сложен, как и любая другая проблема, которую можно аппроксимировать полиномиальным множителем. Однако существуют эффективные алгоритмы аппроксимации для ограниченных классов графов.
В плоских графах максимальное независимое множество может быть аппроксимировано с точностью до любого отношения аппроксимации c <1 за полиномиальное время; аналогичные схемы полиномиальной аппроксимации существуют в любом семействе графов, замкнутых относительно взятия миноров .
В графах с ограниченной степенью известны эффективные алгоритмы аппроксимации с коэффициентами аппроксимации , которые постоянны для фиксированного значения максимальной степени; например, жадный алгоритм, который формирует максимальное независимое множество путем выбора на каждом шаге вершины минимальной степени в графе и удаления ее соседей, достигает отношения аппроксимации (Δ + 2) / 3 на графах с максимальной степенью Δ. Границы аппроксимации для таких случаев были доказаны в работе Berman & Karpinski (1999) . В самом деле, даже Max Independent Set на 3-регулярных графах с 3 красками является APX-полным .
Независимые множества в графах пересечения интервалов
Граф интервалов представляет собой график , в котором узлы являются 1-мерные интервалы (например , интервалы времени) и существует ребро между двумя интервалами , если и только если они пересекаются. Независимый набор в графе интервалов - это просто набор неперекрывающихся интервалов. Проблема поиска максимальных независимых наборов в интервальных графах изучалась, например, в контексте планирования заданий : для заданного набора заданий, которые должны быть выполнены на компьютере, найти максимальный набор заданий, которые могут быть выполнены без вмешательства друг с другом. Эта проблема может быть решена точно за полиномиальное время, используя составление расписания в самый ранний крайний срок .
Независимые множества в геометрических графах пересечений
Геометрический граф пересечения - это граф, узлы которого являются геометрическими фигурами, и между двумя фигурами есть край тогда и только тогда, когда они пересекаются. Независимый набор в геометрическом графе пересечений - это просто набор непересекающихся (непересекающихся) фигур. Проблема поиска максимальных независимых наборов в геометрических графах пересечений изучалась, например, в контексте автоматического размещения меток : для заданного набора местоположений на карте найдите максимальный набор непересекающихся прямоугольных меток около этих местоположений.
Нахождение максимального независимого множества в графах пересечений все еще является NP-полным, но его легче аппроксимировать, чем общую задачу о максимальном независимом множестве. Недавний обзор можно найти во введении к Chan & Har-Peled (2012) .
Нахождение максимальных независимых множеств
Задача поиска максимального независимого множества может быть решена за полиномиальное время с помощью тривиального жадного алгоритма . Все максимальные независимые множества могут быть найдены за время 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 (двоичные файлы) | приблизительное решение путем случайной выборки из максимального независимого пространства множества, подробности см. на веб-странице |
Приложения
Максимально независимое множество и двойственная ему задача о минимальном покрытии вершин участвует в доказательстве вычислительной сложности многих теоретических задач. Они также служат полезными моделями для реальных задач оптимизации, например, минимальный независимый набор является полезной моделью для обнаружения стабильных генетических компонентов для разработки инженерных генетических систем .
Смотрите также
- Независимый набор ребер - это набор ребер, у которых нет двух общих вершин. Обычно это называется сопоставлением .
- Раскраска вершин является разбиением множества вершин в независимые множества.
Примечания
использованная литература
- Бейкер, 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 , pp. 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 ( ссылка ).
- Франк, Андрас (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 (2): 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.