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

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

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

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

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

Свойства [ править ]

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

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

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

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

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

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

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

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

Для многих классов графов максимальное независимое от веса множество может быть найдено за полиномиальное время. Известные примеры — графы без когтей , ^[11] П ₅ -свободные графики ^[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]

См. также [ править ]

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

Примечания [ править ]

^ Korshunov (1974)
^ Годсил и Ройл (2001) , с. 3.
^ Гэри, MR; Джонсон, DS (1 июля 1978 г.). « Сильные» результаты NP-полноты: мотивация, примеры и последствия» . Журнал АКМ . 25 (3): 499–508. дои : 10.1145/322077.322090 . ISSN 0004-5411 . S2CID 18371269 .
^ Доказательство: множество вершин V является независимым множеством. тогда и только тогда, когда каждое ребро в графе смежно не более чем с одним элементом V, тогда и только тогда, когда каждое ребро в графе смежно хотя бы с одним элементом, не принадлежащим V, тогда и только если дополнение к V является вершиной крышка.
^ Мун и Мозер (1965) .
^ Фюреди (1987) .
^ Чиба и Нисидзеки (1985) .
^ Берман и Фудзито (1995) .
^ Сяо и Нагамоти (2017)
^ Сяо и Нагамоти (2013)
^ Минти (1980) , Сбихи (1980) , Накамура и Тамура (2001) , Фаэнца, Ориоло и Стауффер (2014) , Нобили и Сассано (2015)
^ Локштанов, Ватшелле и Вилланджер (2014)
^ Гретшель, Ловас и Шрийвер (1993 , Глава 9: Стабильные множества в графах)
^ Фрэнк (1976)
^ Тарьян (1985)
^ Базган, Кристина ; Эскофье, Бруно; Пашос, Вангелис Т. (2005). «Полнота в стандартных и дифференциальных классах аппроксимации: поли-(D)APX- и (D)PTAS-полнота» . Теоретическая информатика . 339 (2–3): 272–292. дои : 10.1016/j.tcs.2005.03.007 . S2CID 1418848 .
^ Бейкер (1994) ; Гроэ (2003) .
^ Халлдорссон и Радхакришнан (1997) .
^ Хлебик, Мирослав; Хлебикова, Янка (2003). «Твердость аппроксимации для небольших случаев возникновения NP-сложных задач» . Материалы 5-й Международной конференции по алгоритмам и сложности . Конспекты лекций по информатике. Том. 2653. стр. 152–164. дои : 10.1007/3-540-44849-7_21 . ISBN 978-3-540-40176-6 .
^ Нойвонер, Майке (07.06.2021), Улучшенный алгоритм аппроксимации для задачи независимого множества о максимальном весе в свободных графах с d-когтями , arXiv : 2106.03545
^ Циган, Марек (октябрь 2013 г.). «Улучшенное приближение для трехмерного сопоставления посредством локального поиска с ограниченной шириной пути» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 509–518. arXiv : 1304.1424 . дои : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7 . S2CID 14160646 .
^ Луби (1986) .
^ Дайер, Мартин; Гринхилл, Кэтрин (1 апреля 2000 г.). «О цепях Маркова для независимых множеств» . Журнал алгоритмов . 35 (1): 17–49. дои : 10.1006/jagm.1999.1071 . ISSN 0196-6774 .
^ Хитрый, Аллан (2010). «Вычислительный переход на пороге уникальности» . 2010 51-й ежегодный симпозиум IEEE по основам информатики . стр. 287–296. дои : 10.1109/FOCS.2010.34 . ISBN 978-1-4244-8525-3 . S2CID 901126 .
^ Безакова, Ивона; Галанис, Андреас; Голдберг, Лесли Энн; Го, Хэн; Штефанкович, Даниэль (2019). «Аппроксимация посредством затухания корреляции при невозможности сильного пространственного смешивания» . SIAM Journal по вычислительной технике . 48 (2): 279–349. arXiv : 1510.09193 . дои : 10.1137/16M1083906 . ISSN 0097-5397 . S2CID 131975798 .
^ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24). "Computational complexity of counting problems on 3-regular planar graphs". Theoretical Computer Science. Theory and Applications of Models of Computation. 384 (1): 111–125. doi:10.1016/j.tcs.2007.05.023. ISSN 0304-3975., quoted in Куртикапин, Раду; Делл, Хольгер; Фомин, Федор; Голдберг, Лесли Энн; Лапинскас, Джон (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 .
^ Кэннон, Сара; Перкинс, Уилл (2020). Чавла, Шучи (ред.). Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. arXiv : 1906.01666 . дои : 10.1137/1.9781611975994.88 . ISBN 978-1-61197-599-4 . S2CID 174799567 .
^ Скиена, Стивен С. (2012). Руководство по проектированию алгоритмов . Спрингер. ISBN 978-1-84800-069-8 . OCLC 820425142 .
^ Хоссейн, Аяан; Лопес, Эриберто; Халпер, Шон М.; Цетнар, Дэниел П.; Рейс, Александр К.; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13 июля 2020 г.). «Автоматическое проектирование тысяч неповторяющихся деталей для создания стабильных генетических систем» . Природная биотехнология . 38 (12): 1466–1475. дои : 10.1038/s41587-020-0584-2 . ISSN 1546-1696 . ПМИД 32661437 . S2CID 220506228 .

Ссылки [ править ]

Бейкер, Бренда С. (1994), «Алгоритмы аппроксимации для NP-полных задач на плоских графах», Journal of the 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 Прага , Конспекты лекций по информатике , том. 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 .

Внешние ссылки [ править ]

[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) .

[chlebik-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] Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24). "Computational complexity of counting problems on 3-regular planar graphs". Theoretical Computer Science. Theory and Applications of Models of Computation. 384 (1): 111–125. doi:10.1016/j.tcs.2007.05.023. ISSN 0304-3975., quoted in Куртикапин, Раду; Делл, Хольгер; Фомин, Федор; Голдберг, Лесли Энн; Лапинскас, Джон (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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]