Введение

В теории графов, независимое множество, стабильное множество, коклический набор или антиклика – это набор вершин в графе, никакие две из которых не смежны. То есть, это множество вершин, для любых двух вершин из которого не существует ребра, соединяющего их. Эквивалентно, каждое ребро в графе имеет не более одной конечной вершины в множестве A. Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа. Размер независимого множества – это количество вершин, которое оно содержит. Независимые множества также называют «внутренне стабильными множествами», а «стабильное множество» является сокращением этого термина. Максимальное независимое множество – это независимое множество, которое не является собственным подмножеством какого-либо другого независимого множества. Максимальное независимое множество – это независимое множество наибольшего возможного размера для заданного графа. Этот размер называется числом независимости и обычно обозначается как α. Задача оптимизации по поиску такого множества называется задачей о максимальном независимом множестве. Это сильно NP-трудная задача. Следовательно, маловероятно существование эффективного алгоритма для поиска максимального независимого множества графа. Любое максимальное независимое множество также является максимальным, но обратное утверждение не обязательно верно.

Отношение к другим параметрам графа

Множество является независимым тогда и только тогда, когда оно является кликой в дополнении графа, поэтому эти два понятия являются взаимодополняющими. Фактически, достаточно большие графы, не содержащие больших клик, имеют большие независимые множества – тема, изучаемая в теории Рамсея. Множество является независимым тогда и только тогда, когда его дополнение является вершинным покрытием. Следовательно, сумма размеров наибольшего независимого множества и минимального вершинного покрытия равна числу вершин в графе. Вершинная раскраска графа соответствует разбиению множества его вершин на независимые подмножества. Таким образом, минимальное число цветов, необходимое для вершинной раскраски, хроматическое число, не меньше частного от деления числа вершин в графе на независимое число. В двудольном графе без изолированных вершин число вершин в максимальном независимом множестве равно числу ребер в минимальном реберном покрытии; это теорема Кёнига.

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

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

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

Проблема максимального независимого множества является NP-трудной. Однако, её можно решить эффективнее, чем за время O(n² * 2ⁿ), которое потребовалось бы наивному алгоритму полного перебора, проверяющему каждое подмножество вершин на независимость. По состоянию на 2017 год, её можно решить за время O(1.1996n) с использованием полиномиального объёма памяти. При ограничении графов с максимальной степенью 3, задача решается за время O(1.0836n). Для многих классов графов максимальное взвешенное независимое множество может быть найдено за полиномиальное время. Известные примеры – графы без когтей, графы без P5 и совершенные графы. Для хордальных графов максимальное взвешенное независимое множество можно найти за линейное время. Модульное разложение – хороший инструмент для решения задачи о максимальном взвешенном независимом множестве; линейный по времени алгоритм для кографов является базовым примером этого. Другим важным инструментом являются кликовые разделители, описанные Тарьяном. Теорема Кёнига подразумевает, что в двудольном графе максимальное независимое множество можно найти за полиномиальное время, используя алгоритм поиска паросочетания в двудольном графе.

Алгоритмы приближения

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

В плоских графах

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

В графах с ограниченными степенями

В графах с ограниченной степенью известны эффективные алгоритмы приближения с коэффициентами приближения, которые являются постоянными для фиксированного значения максимальной степени; например, жадный алгоритм, формирующий максимальное независимое множество, на каждом шаге выбирает вершину с минимальной степенью в графе и удаляет её соседей, достигая коэффициента приближения (Δ+2)/3 на графах с максимальной степенью Δ. Доказаны границы сложности приближения для таких случаев. Более того, задача Max Independent Set на 3-регулярных 3-красочных графах является APX-полной.

Графики пересечений в интервалах

Интервальный граф — это граф, в котором вершины представляют собой одномерные интервалы (например, временные интервалы), и между двумя интервалами существует ребро, если и только если они пересекаются. Независимое множество в интервальном графе — это просто набор непересекающихся интервалов. Задача поиска максимальных независимых множеств в интервальных графах изучалась, например, в контексте планирования заданий: задан набор заданий, которые необходимо выполнить на компьютере, требуется найти максимальное множество заданий, которые могут быть выполнены без взаимных помех. Эту задачу можно решить точно за полиномиальное время, используя алгоритм планирования по принципу наименьшего срока завершения.

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

Геометрический граф пересечений — это граф, в котором узлы представляют собой геометрические фигуры, и между двумя фигурами существует ребро, если и только если они пересекаются. Независимое множество в геометрическом графе пересечений — это просто набор непересекающихся (не перекрывающихся) фигур. Задача поиска максимальных независимых множеств в геометрических графах пересечений изучалась, например, в контексте автоматического размещения меток: задан набор местоположений на карте, требуется найти максимальное множество непересекающихся прямоугольных меток вблизи этих местоположений. Поиск максимального независимого множества в графах пересечений остаётся NP-полной задачей, но его легче аппроксимировать, чем общую задачу поиска максимального независимого множества. Обзор можно найти во введении.

В графах без гвоздей

В графе d-когтем называется множество из d+1 вершин, одна из которых ("центр") соединена с остальными d вершинами, а остальные d вершин между собой не соединены. Граф, свободный от d-когтей, – это граф, не содержащий подграф в виде d-когтя. Рассмотрим алгоритм, который начинается с пустого множества и инкрементально добавляет в него произвольную вершину, пока она не смежна ни с одной из уже существующих вершин. В графах, свободных от d-когтей, каждая добавленная вершина делает недействительными не более чем d-1 вершин из максимального независимого множества; следовательно, этот тривиальный алгоритм обеспечивает (d-1)-приближение для максимального независимого множества. Однако можно добиться гораздо лучших коэффициентов приближения:

Нойвухнер представил алгоритм, работающий за полиномиальное время, который для любого ε>0 находит (d/2 - 1/63,700,992 + ε)-приближение для максимального взвешенного независимого множества в графе, свободном от d-когтей. Сайган представил алгоритм, работающий за квазиполиномиальное время, который для любого ε>0 достигает приближения (d+ε)/3.

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

Проблема поиска максимального независимого множества может быть решена за полиномиальное время с помощью тривиального параллельного жадного алгоритма. Все максимальные независимые множества могут быть найдены за время O(3ⁿ/₃) = O(1.4423n).

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

В задаче подсчета #IS задается вопрос: сколько независимых множеств содержит данный неориентированный граф. Эта задача является неразрешимой, а именно, она является ♯P-полной, даже для графов с максимальной степенью три. Кроме того, известно, что при условии NP ≠ RP, задачу нельзя эффективно аппроксимировать в том смысле, что для неё не существует полностью полиномиальной схемы аппроксимации времени с рандомизацией (FPRAS), даже для графов с максимальной степенью шесть; однако, полностью полиномиальная схема аппроксимации времени (FPTAS) существует в случае, когда максимальная степень равна пяти. Задача #BIS, подсчета независимых множеств на двудольных графах, также является ♯P-полной, даже для графов с максимальной степенью три. Неизвестно, допускает ли #BIS существование FPRAS. Также исследовался вопрос подсчета максимальных независимых множеств.

Приложения

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