Введение

Независимое множество, которое не является подмножеством какого-либо другого независимого множества. Комбинаторные аспекты максимальных независимых множеств вершин в графе.

В теории графов, максимальное независимое множество (МИМ) или максимальное стабильное множество – это независимое множество, которое не является подмножеством какого-либо другого независимого множества. Иными словами, не существует вершины вне этого независимого множества, которая могла бы быть добавлена к нему, поскольку оно максимально по отношению к свойству независимости. Например, в графе, представляющем собой путь с тремя вершинами a, b и c, и двумя ребрами и , множества {b} и {a, c} являются максимальными независимыми. Множество {a} является независимым, но не максимальным независимым, поскольку оно является подмножеством большего независимого множества {a, c}. В этом же графе максимальными кликами являются множества {a, b} и {b, c}. МИМ также является доминирующим множеством в графе, и любое доминирующее множество, которое является независимым, должно быть максимальным независимым, поэтому МИМ также называют независимыми доминирующими множествами. Граф может иметь множество МИМ различных размеров; наибольший, или, возможно, несколько МИМ одинакового размера, называется максимальным независимым множеством. Графы, в которых все максимальные независимые множества имеют одинаковый размер, называются хорошо покрытыми графами. Фраза "максимальное независимое множество" также используется для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, и в частности, в векторных пространствах и матроидах. С МИМ связаны две алгоритмические задачи: поиск одного МИМ в заданном графе и перечисление всех МИМ в заданном графе.

Характеристики семей графов

Некоторые семейства графов также характеризуются с точки зрения их максимальных клик или максимальных независимых множеств. Примерами служат графы, необратимые по максимальным кликам, и наследственно необратимые по максимальным кликам графы. Граф называется необратимым по максимальным кликам, если для каждой максимальной клики существует ребро, не принадлежащее ни одной другой максимальной клике, а наследственно необратимым по максимальным кликам, если это свойство выполняется для каждого индуцированного подграфа. К наследственно необратимым по максимальным кликам графам относятся графы без треугольников, двудольные графы и интервальные графы. Кографы можно охарактеризовать как графы, в которых каждая максимальная клика пересекается с каждым максимальным независимым множеством, и в которых это свойство выполняется во всех индуцированных подграфах.

Ограничение количества наборов

показано, что любой граф с n вершинами имеет не более 3n/3 максимальных клик. Соответственно, любой граф с n вершинами также имеет не более 3n/3 максимальных независимых множеств. Граф с ровно 3n/3 максимальными независимыми множествами легко построить: достаточно взять дизъюнктное объединение n/3 треугольных графов. Любое максимальное независимое множество в этом графе формируется выбором одной вершины из каждого треугольника. Дополнительный граф, содержащий ровно 3n/3 максимальных клик, является частным случаем графа Турана; из-за их связи с границей Муна и Мозера, эти графы также иногда называют графами Муна-Мозера. Более точные границы возможны, если ограничить размер максимальных независимых множеств: количество максимальных независимых множеств размера k в любом графе с n вершинами не превышает. Графы, достигающие этой границы, снова являются графами Турана. Однако некоторые семейства графов могут иметь гораздо более строгие ограничения на количество максимальных независимых множеств или максимальных клик. Если все графы с n вершинами в семействе графов имеют O(n) ребер, и если каждый подграф графа в семействе также принадлежит этому семейству, то каждый граф в семействе может иметь не более O(n) максимальных клик, все из которых имеют размер O(1). Например, эти условия выполняются для планарных графов: каждый планарный граф с n вершинами имеет не более 3n − 6 ребер, а подграф планарного графа всегда планарен, из чего следует, что каждый планарный граф имеет O(n) максимальных клик (размером не более четырех). Интервальные и аккордальные графы также имеют не более n максимальных клик, хотя они не всегда являются разреженными графами. Количество максимальных независимых множеств в циклическом графе с n вершинами задается числами Перрина, а количество максимальных независимых множеств в графе-пути с n вершинами задается последовательностью Падована. Следовательно, оба числа пропорциональны степеням 1.324718, пластическому отношению.

Перечень всех максимальных независимых множеств

Алгоритм для перечисления всех максимальных независимых множеств или максимальных клик в графе может использоваться в качестве подпрограммы для решения многих NP-полных задач о графах. Очевидно, что решения задачи о максимальном независимом множестве, максимальной клике и минимальной независимой доминирующей задаче должны быть максимальными независимыми множествами или максимальными кликами и могут быть найдены алгоритмом, который перечисляет все максимальные независимые множества или максимальные клики и сохраняет те, которые имеют наибольший или наименьший размер. Аналогично, минимальное вершинное покрытие можно найти как дополнение к одному из максимальных независимых множеств. Было замечено, что перечисление максимальных независимых множеств также может быть использовано для нахождения 3-раскрасок графов: граф можно 3-раскрасить тогда и только тогда, когда дополнение одного из его максимальных независимых множеств является двудольным. Этот подход использовался не только для 3-раскраски, но и как часть более общего алгоритма раскраски графов, и с тех пор другие авторы усовершенствовали подобные подходы к раскраске графов. Другие, более сложные задачи также могут быть смоделированы как поиск клики или независимого множества определенного типа. Это мотивирует алгоритмическую задачу эффективного перечисления всех максимальных независимых множеств (или, эквивалентно, всех максимальных клик). Доказательство границы 3n/3 Муна и Мозера для числа максимальных независимых множеств можно непосредственно преобразовать в алгоритм, перечисляющий все такие множества за время O(3n/3). Для графов, имеющих наибольшее возможное число максимальных независимых множеств, этот алгоритм требует постоянного времени на выходное множество. Однако алгоритм с такой временной сложностью может быть крайне неэффективным для графов с меньшим числом независимых множеств. По этой причине многие исследователи изучали алгоритмы, перечисляющие все максимальные независимые множества за полиномиальное время на выходное множество. Время, затрачиваемое на нахождение одного максимального независимого множества, пропорционально времени, необходимому для умножения матриц в плотных графах, или меньше в различных классах разреженных графов.

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

Проблема подсчета, связанная с максимальными независимыми множествами, изучалась в теории вычислительной сложности. Задача состоит в том, чтобы, задав неориентированный граф, определить, сколько в нем содержится максимальных независимых множеств. Эта задача является #P-трудной даже при ограничении входных данных двудольными графами. Однако, для некоторых специфических классов графов, например, для кографов, задача разрешима.

История

Первоначально считалось, что задачу нахождения максимального независимого множества сложно эффективно распараллелить, поскольку лексикографическое максимальное независимое множество оказалось P-полной задачей. Однако было показано, что детерминированное параллельное решение можно получить с помощью сведения либо к задаче о максимальном покрытии множества, либо к задаче о максимальном паросочетании, либо с помощью сведения к задаче 2-удовлетворимости. Обычно структура таких алгоритмов аналогична другим параллельным алгоритмам для графов: они разбивают граф на более мелкие локальные задачи, которые можно решать параллельно, используя один и тот же алгоритм. Первоначальные исследования задачи нахождения максимального независимого множества проводились на модели PRAM, а затем были расширены для получения результатов для распределенных алгоритмов на компьютерных кластерах. Все сложности разработки распределенных параллельных алгоритмов в полной мере применимы и к задаче нахождения максимального независимого множества. В частности, необходимо найти алгоритм, который обеспечивает эффективное время работы и оптимальную передачу данных при разбиении графа и объединении независимых множеств.

Класс сложности

В 1984 году Карп и др. показали, что детерминированное параллельное решение задачи о максимальном независимом множестве на PRAM принадлежит к зоопарку сложности Nick's Class. Иными словами, их алгоритм находит максимальное независимое множество за время , где – размер множества вершин. В той же статье был представлен также рандомизированный параллельный алгоритм со временем работы , использующий процессоров. Вскоре после этого Люби и Алон с соавторами независимо улучшили этот результат, переведя задачу о максимальном независимом множестве в класс со временем работы и использованием процессоров, где – количество ребер в графе. Чтобы доказать, что их алгоритм относится к классу , они первоначально представили рандомизированный алгоритм, использующий процессоров, который можно было дерандомизировать, добавив еще процессоров. На сегодняшний день остается открытым вопрос о том, принадлежит ли задача о максимальном независимом множестве классу .

Общение и обмен данными

Распределенные алгоритмы поиска максимальных независимых множеств испытывают сильное влияние алгоритмов, разработанных для модели PRAM. Оригинальные работы Люби и Алона с соавторами послужили основой для разработки нескольких распределенных алгоритмов.