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

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

В теории графов, А максимальное независимое множество (ИСА) или максимальный набор стабильный является независимым множеством, что не является подмножество любого другого независимого множества. Другими словами, нет вершины вне независимого множества, которая могла бы присоединиться к нему, потому что она максимальна по отношению к свойству независимого множества.

Например, в графе, путь с тремя вершинами,, и, и двух краев и, наборов и оба максимально независимы. Набор является независимым, но не максимально независимым, потому что он является подмножеством большего независимого набора. В этом же графе максимальными кликами являются множества и. ${\ displaystyle P_ {3}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle ab}$${\ displaystyle bc}$${\ Displaystyle \ {Ь \}}$${\ Displaystyle \ {а, с \}}$${\ Displaystyle \ {а \}}$${\ Displaystyle \ {а, с \}}$${\ Displaystyle \ {а, б \}}$${\ displaystyle \ {b, c \}}$

MIS также является доминирующим множеством в графе, и каждое доминирующее множество, которое является независимым, должно быть максимально независимым, поэтому MIS также называют независимыми доминирующими множествами.

Два верхних графика - это максимальные независимые множества, а два нижних - независимые, но не максимальные. Максимальный независимый набор представлен в верхнем левом углу.${\ displaystyle P_ {3}}$

График может иметь множество MIS самых разных размеров; самая большая или, возможно, несколько одинаково больших MIS графа называется максимальным независимым набором. Графы, в которых все максимальные независимые множества имеют одинаковый размер, называются хорошо покрытыми графами.

Фраза «максимальное независимое множество» также используется для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, и, в частности, в векторных пространствах и матроидах.

Два независимых набора для звездного графа показывают, насколько сильно могут быть разные по размеру два максимальных независимых набора (правый - максимальный).${\ displaystyle S_ {8}}$

С MIS связаны две алгоритмические проблемы : поиск единственной MIS в данном графе и перечисление всех MIS в данном графе.

• 1 Определение
• 2 Связанные множества вершин
• 3 Характеристика семейств графов
• 4 Ограничение количества подходов
• 5 Нахождение единственного максимального независимого множества
  • 5.1 Последовательный алгоритм
  • 5.2 Параллельный алгоритм случайного выбора [алгоритм Люби]
  • 5.3 Параллельный алгоритм со случайным приоритетом
  • 5.4. Параллельный алгоритм со случайной перестановкой [алгоритм Блеллоха]
• 6 Список всех максимальных независимых множеств
• 7 Распараллеливание нахождения максимальных независимых множеств
  • 7.1 История
  • 7.2 Класс сложности
  • 7.3 Связь и обмен данными
• 8 Примечания
• 9 ссылки

Для графа, независимое множество является максимальным независимым множеством, если для, один из следующих условий: ${\ Displaystyle G = (V, E)}$ ${\ displaystyle S}$${\ displaystyle v \ in V}$

1. ${\ displaystyle v \ in S}$
2. ${\ Displaystyle N (v) \ cap S \ neq \ emptyset}$где обозначает соседей${\ Displaystyle N (v)}$${\ displaystyle v}$

Вышеупомянутое можно переформулировать как вершину, принадлежащую независимому набору или имеющую по крайней мере одну соседнюю вершину, принадлежащую независимому набору. В результате у каждого ребра графа есть хотя бы одна конечная точка, не входящая в. Однако неверно, что каждое ребро графа имеет хотя бы одну или даже одну конечную точку в${\ displaystyle S}$${\ displaystyle S}$

Обратите внимание, что любой сосед вершины в независимом множестве не может быть внутри, потому что эти вершины не пересекаются по определению независимого множества. ${\ displaystyle S}$${\ displaystyle S}$

Если S - максимальное независимое множество в некотором графе, это максимальная клика или максимальный полный подграф в дополнительном графе. Максимальная Клика представляет собой набор вершин, индуцирует полный подграф, и это не является подмножество вершин любого большего полного подграфа. То есть, это набор S таким образом, что каждая пара вершин в S соединяются ребром и каждая вершина не в S отсутствует ребро, по крайней мере с одной вершины в S. Граф может иметь много максимальных клик разного размера; поиск наибольшего из них - задача максимальной клики.

Некоторые авторы включают максимальность как часть определения клики и называют максимальные клики просто кликами.

Слева - максимальное независимое множество. Середина - это клика на дополнении графа. Справа - вершинное покрытие максимального независимого дополнения множества.${\ displaystyle K_ {3}}$

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

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

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

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

Мун и Мозер (1965) показали, что любой граф с n вершинами имеет не более 3 ^{n / 3} максимальных клик. Кроме того, любой граф с n вершинами также имеет не более 3 ^{n / 3} максимальных независимых множеств. Граф с ровно 3 ^{n / 3} максимальными независимыми множествами легко построить: просто возьмем несвязное объединение n / 3 треугольных графов. Любое максимальное независимое множество в этом графе формируется путем выбора по одной вершине из каждого треугольника. Дополнительный граф, имеющий ровно 3 ^{n / 3} максимальных клик, является особым типом графа Турана ; из-за их связи с оценкой Муна и Мозера эти графы также иногда называют графами Муна-Мозера. Более точные границы возможны, если ограничить размер максимальных независимых множеств: количество максимальных независимых множеств размера k в любом n- вершинном графе не превосходит

${\ displaystyle \ lfloor n / k \ rfloor ^ {k- (n {\ bmod {k}})} \ lfloor n / k + 1 \ rfloor ^ {n {\ bmod {k}}}.}.$

Графы, достигающие этой границы, снова являются графами Турана.

Однако некоторые семейства графов могут иметь гораздо более строгие ограничения на количество максимальных независимых множеств или максимальных клик. Если все графы с n -вершинами в семействе графов имеют O ( n) ребер, и если каждый подграф графа в семействе также принадлежит семейству, то каждый граф в семействе может иметь не более O ( n) максимальных клик, все из которых имеют размер O (1). Например, эти условия верны для плоских графов : каждый планарный граф с n вершинами имеет не более 3 n  - 6 ребер, а подграф плоского графа всегда плоский, из чего следует, что каждый плоский граф имеет O ( n) максимальные клики (размером не более четырех). Интервальные графы и хордовые графы также имеют не более n максимальных клик, хотя они не всегда являются разреженными графами.

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

Последовательный алгоритм

Учитывая График G (V, E), легко найти одну ИСУ, используя следующий алгоритм:

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выбираем узел v∈V;
   • Добавьте v к множеству I;
   • Удалите из V узел v и всех его соседей.
3. Вернуть I.

Время выполнения - O ( m), так как в худшем случае мы должны проверить все ребра.

O (m), очевидно, является наилучшей возможной средой выполнения для последовательного алгоритма. Но параллельный алгоритм может решить проблему намного быстрее.

Параллельный алгоритм со случайным выбором [алгоритм Люби]

Следующий алгоритм находит MIS за время O (log n).

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выберите случайный набор вершин S ⊆ V, выбирая каждую вершину v независимо с вероятностью 1 / (2d (v)), где d - степень v (количество соседей v).
   • Для каждого ребра в E, если обе его конечные точки находятся в случайном наборе S, тогда удалите из S конечную точку, степень которой ниже (т. Е. Имеет меньше соседей). Разрыв связей произвольно, например, используя лексикографический порядок в именах вершин.
   • Добавьте набор S к I.
   • Удалите из V множество S и всех соседей узлов в S.
3. Вернуть I.

АНАЛИЗ: Для каждого узла v разделите его соседей на более низких соседей (чья степень ниже, чем степень v) и более высоких соседей (чья степень выше, чем степень v), разорвав связи, как в алгоритме.

Назовите узел v плохим, если более 2/3 его соседей являются старшими соседями. Назовите ребро плохим, если обе его конечные точки плохи; в остальном край хороший.

• По крайней мере 1/2 всех краев всегда хороши. ДОКАЗАТЕЛЬСТВО: Постройте направленную версию G, направляя каждое ребро к узлу с более высокой степенью (произвольно разрывая связи). Таким образом, для каждого плохого узла количество исходящих ребер более чем в 2 раза превышает количество входящих ребер. Таким образом, каждое плохое ребро, которое входит в узел v, может быть сопоставлено с отдельным набором из двух ребер, которые выходят из узла v. Следовательно, общее количество ребер как минимум в 2 раза превышает количество плохих ребер.
• Для каждого хорошего узла u вероятность того, что сосед u будет выбран для S, является, по крайней мере, некоторой положительной константой. ДОКАЗАТЕЛЬСТВО: вероятность того, что для S не выбран ни один из соседей u, не превышает вероятности того, что ни один из нижних соседей u не выбран. Для каждого младшего соседа v вероятность того, что он не будет выбран, равна (1-1 / 2d (v)), что не превышает (1-1 / 2d (u)) (поскольку d (u)gt; d (v)). Число таких соседей не менее d (u) / 3, так как u хороший. Следовательно, вероятность того, что не будет выбран ни один младший сосед, составляет не более 1-exp (-1/6).
• Для каждого узла u, который выбран для S, вероятность того, что u будет удалена из S, не превышает 1/2. ДОКАЗАТЕЛЬСТВО: Эта вероятность является не более чем вероятностью того, что старший сосед u выбран для S.Для каждого старшего соседа v вероятность того, что он выбран, составляет не более 1 / 2d (v), что не более 1 / 2d (u) (поскольку d (v)gt; d (u)). По объединению вероятность того, что не будет выбран ни один из вышестоящих соседей, не превосходит d (u) / 2d (u) = 1/2.
• Следовательно, для каждого хорошего узла u вероятность того, что сосед u будет выбран для S и останется в S, является некоторой положительной константой. Следовательно, вероятность того, что u удаляется на каждом шаге, является как минимум положительной константой.
• Следовательно, для каждого хорошего ребра e вероятность того, что e удаляется на каждом шаге, является как минимум положительной константой. Таким образом, количество хороших ребер уменьшается, по крайней мере, на постоянный коэффициент на каждом шаге.
• Поскольку по крайней мере половина ребер в порядке, общее количество ребер также уменьшается на постоянный коэффициент на каждом шаге.
• Следовательно, количество шагов равно O (log m), где m - количество ребер. Это ограничено.${\ Displaystyle О (\ журнал (п))}$

Граф наихудшего случая, в котором среднее количество шагов равно, представляет собой граф, состоящий из n / 2 связанных компонентов, каждая из которых имеет 2 узла. Степень всех узлов равна 1, поэтому каждый узел выбирается с вероятностью 1/2, а с вероятностью 1/4 оба узла в компоненте не выбираются. Следовательно, количество узлов уменьшается в 4 раза на каждом шаге, а ожидаемое количество шагов равно. ${\ Displaystyle \ Theta (\ log (п))}$${\ Displaystyle \ журнал _ {4} (п)}$

Параллельный алгоритм со случайным приоритетом

Следующий алгоритм лучше предыдущего тем, что в каждый связанный компонент всегда добавляется как минимум один новый узел:

1. Инициализируйте I пустым набором.
2. Пока V не пуст, каждый узел v делает следующее:
   • Выбирает случайное число r (v) в [0,1] и отправляет его своим соседям;
   • Если r (v) меньше, чем количество всех соседей v, то v вставляется в I, удаляется из V и сообщает об этом своим соседям;
   • Если v слышал, что один из его соседей попал в I, то v удаляется из V.
3. Вернуть I.

Обратите внимание, что на каждом шаге узел с наименьшим номером в каждом связном компоненте всегда входит в I, поэтому всегда есть некоторый прогресс. В частности, в худшем случае предыдущего алгоритма ( n / 2 связанных компонентов с 2 узлами в каждой) MIS будет найдена за один шаг.

АНАЛИЗ:

• У узла есть вероятность как минимум быть удаленным. Доказательство: для каждого ребра, соединяющего пару узлов, замените его двумя направленными ребрами, одно от и другое. Обратите внимание, что теперь он в два раза больше. Для каждой пары направленных ребер определите два события: и, упреждающее удаление и упреждающее удаление, соответственно. Событие происходит, когда и, где является соседом и является соседом. Напомним, что каждому узлу дается случайное число из того же диапазона [0, 1]. В простом примере с двумя непересекающимися узлами каждый из них имеет наименьшую вероятность. Если есть три непересекающихся узла, каждый имеет наименьшую вероятность. В случае, это имеет вероятность, по крайней мере, быть наименьшей, потому что возможно, что сосед является также соседом, поэтому узел становится дважды подсчитанным. Используя ту же логику, событие также имеет вероятность, по крайней мере, быть удаленным.${\ displaystyle v}$${\ displaystyle {\ frac {1} {d (v) + d (w)}}}$${\ displaystyle (v, w)}$${\ displaystyle (v, w)}$${\ Displaystyle (ш, в)}$${\ displaystyle | E |}$${\ displaystyle (v, w)}$${\ displaystyle (v \ rightarrow w)}$${\ Displaystyle (ш \ rightarrow v)}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle (v \ rightarrow w)}$${\ Displaystyle г (v) lt;г (ш)}$${\ Displaystyle г (v) lt;г (х)}$${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle x}$${\ displaystyle w}$${\ displaystyle {\ frac {1} {2}}}$${\ displaystyle {\ frac {1} {3}}}$${\ displaystyle v}$${\ displaystyle {\ frac {1} {d (v) + d (w)}}}$${\ displaystyle v}$${\ displaystyle w}$${\ Displaystyle (ш \ rightarrow v)}$${\ displaystyle {\ frac {1} {d (w) + d (v)}}}$
• Когда происходят события и, они соответственно удаляют и направляют исходящие ребра. Доказательство: В том случае, когда удаляется, все соседние узлы также удаляются. Количество исходящих направленных ребер из удаленных равно. По той же логике удаляет направленные исходящие ребра.${\ displaystyle (v \ rightarrow w)}$${\ Displaystyle (ш \ rightarrow v)}$${\ Displaystyle д (ш)}$${\ displaystyle d (v)}$${\ displaystyle (v \ rightarrow w)}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle w}$${\ Displaystyle д (ш)}$${\ Displaystyle (ш \ rightarrow v)}$${\ displaystyle d (v)}$
• Ожидается, что на каждой итерации шага 2 будет удалена половина ребер. ДОКАЗАТЕЛЬСТВО: Если событие происходит, то все соседи удаляются; следовательно, ожидаемое количество ребер, удаленных из-за этого события, по крайней мере. То же самое верно и для обратного события, т. Е. Ожидаемое количество удаленных ребер не менее. Следовательно, для каждого неориентированного ребра ожидаемое количество ребер, удаленных из-за того, что один из этих узлов имеет наименьшее значение, составляет. Суммирование по всем ребрам дает ожидаемое количество ребер, удаляемых на каждом шаге, но каждое ребро учитывается дважды (по одному разу на направление), давая ожидаемое удаление ребер на каждом шаге.${\ displaystyle (v \ rightarrow w)}$${\ displaystyle w}$${\ Displaystyle {\ гидроразрыва {д (ш)} {д (в) + д (ш)}}}$${\ Displaystyle (ш \ rightarrow v)}$${\ Displaystyle {\ гидроразрыва {d (v)} {d (w) + d (v)}}}$${\ Displaystyle (ш, в)}$${\ Displaystyle {\ гидроразрыва {d (вес) + d (v)} {d (w) + d (v)}} = 1}$${\ displaystyle \ sum _ {{v, w} \ in E} 1 = | E |}$${\ displaystyle | E |}$${\ displaystyle {\ frac {| E |} {2}}}$
• Следовательно, ожидаемое время работы алгоритма равно.${\ displaystyle 3 \ log _ {4/3} (м) +1}$${\ Displaystyle О (\ журнал (п))}$

Параллельный алгоритм со случайной перестановкой [алгоритм Блеллоха]

Вместо рандомизации на каждом шаге можно произвести рандомизацию один раз в начале алгоритма, зафиксировав случайный порядок на узлах. При таком фиксированном порядке следующий параллельный алгоритм достигает точно такой же MIS, что и алгоритм #Sequential (т. Е. Результат детерминирован):

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Пусть W будет набором вершин в V без более ранних соседей (на основе фиксированного порядка);
   • Добавьте W к I;
   • Удалите из V узлы множества W и всех их соседей.
3. Вернуть I.

Между полностью последовательными и полностью параллельными алгоритмами существует континуум алгоритмов, которые частично являются последовательными, а частично параллельными. При фиксированном порядке узлов и множителе δ∈ (0,1] следующий алгоритм возвращает ту же MIS:

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выберите коэффициент δ∈ (0,1].
   • Пусть P будет набором δ n узлов, которые являются первыми в фиксированном порядке.
   • Пусть W - ИСУ на P, использующая полностью параллельный алгоритм.
   • Добавьте W к I;
   • Удалите из V все узлы в префиксе P и всех соседей узлов в множестве W.
3. Вернуть I.

Установка δ = 1 / n дает полностью последовательный алгоритм; установка δ = 1 дает полностью параллельный алгоритм.

АНАЛИЗ: При правильном выборе параметра δ в частично параллельном алгоритме можно гарантировать, что он завершится не более чем после log (n) вызовов полностью параллельного алгоритма, а количество шагов в каждом вызове будет не более log (п). Следовательно, общее время работы частично параллельного алгоритма составляет. Следовательно, время выполнения полностью параллельного алгоритма также не выше. Основные этапы проверки: ${\ Displaystyle О (\ журнал ^ {2} (п))}$${\ Displaystyle О (\ журнал ^ {2} (п))}$

• Если на шаге i мы выбираем, где D - максимальная степень узла в графе, тогда WHP все узлы, оставшиеся после шага i, имеют степень не выше. Таким образом, после шагов log ( D) все оставшиеся узлы имеют степень 0 (поскольку D lt; n) и могут быть удалены за один шаг.${\ displaystyle \ delta = 2 ^ {i} \ log {(n)} / D}$ ${\ displaystyle D / 2 ^ {i}}$
• Если на любом этапе степень каждого узла не превосходит d, и мы выбираем (для любой константы C), то WHP имеет длину самого длинного пути в ориентированном графе, определяемом фиксированным порядком. Следовательно, полностью параллельный алгоритм занимает максимум шагов (поскольку самый длинный путь - это наихудший предел количества шагов в этом алгоритме).${\ displaystyle \ delta = C \ log {(n)} / d}$ ${\ Displaystyle О (\ журнал (п))}$${\ Displaystyle О (\ журнал (п))}$
• Объединение этих двух фактов дает, что, если мы выберем, то WHP время выполнения частично параллельного алгоритма равно.${\ displaystyle \ delta = 2 ^ {i} \ log {(n)} / D}$${\ Displaystyle О (\ журнал (D) \ журнал (п)) = О (\ журнал ^ {2} (п))}$

Дополнительная информация: проблема клики § перечисление всех максимальных клик

Алгоритм для перечисления всех максимальных независимых множеств или максимальных клик в графе может использоваться в качестве подпрограммы для решения многих задач NP-полного графа. Наиболее очевидно, что решения задачи о максимальном независимом множестве, проблеме максимальной клики и минимальной независимой доминирующей проблеме должны быть максимальными независимыми множествами или максимальными кликами, и их можно найти с помощью алгоритма, который перечисляет все максимальные независимые множества или максимальные клики и сохраняет те, которые имеют наибольший или наименьший размер. Точно так же минимальное вершинное покрытие может быть найдено как дополнение к одному из максимальных независимых множеств. Лоулер (1976) заметил, что перечисление максимальных независимых множеств также может быть использовано для нахождения 3-раскраски графов: граф может быть 3-цветным тогда и только тогда, когда дополнение одного из его максимальных независимых множеств является двудольным. Он использовал этот подход не только для 3-раскраски, но и как часть более общего алгоритма раскраски графов, и с тех пор аналогичные подходы к раскраске графов были усовершенствованы другими авторами. Другие, более сложные задачи также можно смоделировать как поиск группы или независимого набора определенного типа. Это мотивирует алгоритмическую проблему эффективного перечисления всех максимальных независимых множеств (или, что эквивалентно, всех максимальных клик).

Несложно превратить доказательство оценки Муна и Мозера 3 ^{n / 3} на количество максимальных независимых множеств в алгоритм, который перечисляет все такие множества за время O (3 ^{n / 3}). Для графов, которые имеют максимально возможное количество максимальных независимых наборов, этот алгоритм требует постоянного времени для каждого набора выходных данных. Однако алгоритм с этой временной границей может быть крайне неэффективным для графов с более ограниченным числом независимых наборов. По этой причине многие исследователи изучали алгоритмы, которые перечисляют все максимальные независимые множества за полиномиальное время для каждого выходного набора. Время на максимальное независимое множество пропорционально времени умножения матриц в плотных графах или быстрее в различных классах разреженных графов.

История

Задача максимального независимого множества изначально считалась нетривиальной для распараллеливания из-за того, что лексикографическое максимальное независимое множество оказалось P-полным ; однако было показано, что детерминированное параллельное решение может быть дано сокращением либо от максимальной упаковки набора, либо от задачи максимального согласования, либо путем сокращения от проблемы 2-выполнимости. Как правило, структура данного алгоритма соответствует другим алгоритмам параллельного графа - то есть они подразделяют граф на более мелкие локальные проблемы, которые можно решить параллельно, запустив идентичный алгоритм. ${\ Displaystyle NC ^ {1}}$ ${\ Displaystyle NC ^ {2}}$

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

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

Это было показано в 1984 г. Карпом и др. что детерминированное параллельное решение на PRAM для максимального независимого множества принадлежит зоопарку сложности класса Ника. То есть их алгоритм находит максимальное независимое множество при использовании, где - размер набора вершин. В той же статье также было представлено рандомизированное параллельное решение со средой выполнения с использованием процессоров. Вскоре после этого Луби и Алон и др. независимо улучшил этот результат, перенеся задачу о максимальном независимом множестве в область со средой выполнения, использующей процессоры, где - количество ребер в графе. Чтобы показать, что их алгоритм работает, они изначально представили рандомизированный алгоритм, который использует процессоры, но может быть дерандомизирован с помощью дополнительных процессоров. Сегодня остается открытым вопрос о том, находится ли проблема максимального независимого множества. ${\ displaystyle NC_ {4}}$${\ Displaystyle О (\ журнал ^ {4} п)}$${\ Displaystyle О ((п / \ журнал п) ^ {3})}$${\ displaystyle n}$${\ Displaystyle О (\ журнал ^ {4} п)}$${\ Displaystyle О (п ^ {2})}$${\ displaystyle NC_ {2}}$${\ Displaystyle О (\ журнал ^ {2} п)}$${\ Displaystyle О (мн ^ {2})}$${\ displaystyle m}$${\ displaystyle NC_ {2}}$${\ Displaystyle О (м)}$${\ Displaystyle О (п ^ {2})}$${\ Displaystyle NC_ {1}}$

Связь и обмен данными

Алгоритмы распределенного максимального независимого множества находятся под сильным влиянием алгоритмов модели PRAM. Оригинальная работа Luby и Alon et al. привело к созданию нескольких распределенных алгоритмов. Что касается обмена битами, эти алгоритмы имели нижнюю границу размера сообщения на раунд битов и потребовали дополнительных характеристик графа. Например, необходимо знать размер графа или можно запросить максимальную степень соседних вершин для данной вершины. В 2010 году Métivier et al. уменьшил требуемый размер сообщения за раунд до, что является оптимальным, и устранил необходимость в каких-либо дополнительных знаниях графа. ${\ Displaystyle О (\ журнал п)}$${\ displaystyle O (1)}$

• Bisdorff, R.; Маричал, Ж.-Л. (2007), Подсчет неизоморфных максимальных независимых множеств графа n -циклов, arXiv : math.CO/0701647.
• Бомзе, И.М. Будинич, М.; Пардалос, PM; Пелилло, М. (1999), "Проблема максимальной клики", Справочник по комбинаторной оптимизации, 4, Kluwer Academic Publishers, стр. 1–74, CiteSeerX   10.1.1.48.4074.
• Бысков, JM (2003), "Алгоритмы k- раскраски и поиска максимальных независимых множеств", Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Soda '03, стр. 456–457, ISBN   9780898715385.
• Chiba, N.; Nishizeki, Т. (1985), "Arboricity и алгоритмы подграф листинга", SIAM журнал по вычислениям, 14 (1): 210-223, DOI : 10,1137 / 0214017, S2CID   207051803.
• Croitoru, C. (1979), "О конюшнях в графах", Proc. Третий сб. Исследование операций, Университет Бабеш-Бойяи, Клуж-Напока, Румыния, стр. 55–60..
• Эппштейн, Д. (2003), «Малые максимальные независимые множества и более быстрая точная раскраска графов» (PDF), Журнал алгоритмов и приложений графов, 7 (2): 131–140, arXiv : cs.DS / 0011009, CiteSeerX   10.1. 1.342.4049, DOI : 10,7155 / jgaa.00064.
• Эпштейн, Д. (2005), "Все максимальные независимые множества и динамическое преобладание для разреженных графов", Proc. Шестнадцатый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам, 5, стр. 451–459, arXiv : cs.DS / 0407036, doi : 10.1145 / 1597036.1597042, S2CID   2769046.
• Erdős, P. (1966), "О кликами в графах", Израиль Журнал математики, 4 (4): 233-234, DOI : 10.1007 / BF02771637, MR   0205874, S2CID   121993028.
• Эйлер, Р. (2005), «Число Фибоначчи сеточного графа и новый класс целочисленных последовательностей», Журнал целочисленных последовательностей, 8 (2): 05.2.6, Bibcode : 2005JIntS... 8... 26E.
• Фуредите, З. (1987), "Число максимальных независимых множеств в связных графах", журнал теории графов, 11 (4): 463-470, DOI : 10.1002 / jgt.3190110403.
• Jennings, E.; Motycková, L. (1992), "Распределенный алгоритм для поиска всех максимальных клик в сетевом графе", Proc. Первый латиноамериканский симпозиум по теоретической информатике, конспект лекций по информатике, 583, Springer-Verlag, стр. 281–293
• Джонсон, DS ; Яннакакис, М. ; Пападимитриу, С.Х. (1988), «О создании всех максимальных независимых множеств», Письма об обработке информации, 27 (3): 119–123, DOI : 10.1016 / 0020-0190 (88) 90065-8.
• Лоулер, EL (1976), «Заметка о сложности проблемы хроматического числа», Информационные письма, 5 (3): 66–67, DOI : 10.1016 / 0020-0190 (76) 90065-X.
• Лоулер, Э.Л. ; Lenstra, JK ; Rinnooy Кан, AHG (1980), "Генерация всех максимальных независимых множеств: алгоритмы NP-твердость и полиномиальное время" (PDF), SIAM журнал по вычислениям, 9 (3): 558-565, DOI : 10,1137 / 0209042.
• Люн, JY-T. (1984), «Быстрые алгоритмы для создания всех максимальных независимых наборов интервальных, дуг окружных и хордовых графов», Журнал алгоритмов, 5: 22–35, DOI : 10.1016 / 0196-6774 (84) 90037-3.
• Лян, Ю. Д.; Дхалл, СК; Lakshmivarahan, С. (1991), «К вопросу о нахождении всех Максимальный вес независимых множеств в интервале и круговых графиков дуги», исходя из 1991 симпозиума по прикладной вычислительной, С. 465-470,. DOI : 10.1109 / SOAC.1991.143921
• Макино, К.; Уно, Т. (2004), "Новые алгоритмы перечисления всех максимальных клик", Proc. Девятый Скандинавский семинар по теории алгоритмов, Lecture Notes в Compute науки, 3111., Springer-Verlag, стр 260-272, CiteSeerX   10.1.1.138.705, DOI : 10.1007 / 978-3-540-27810-8_23, ISBN   978-3-540-22339-9. ISBN   9783540223399, 9783540278108.
• Mishra, N.; Питт, Л. (1997), "Создание всех максимальных независимых множеств гиперграфов ограниченной степени", Proc. Десятая конф. Вычислительная теория обучения. С. 211-217, DOI : 10,1145 / 267460,267500, ISBN   978-0-89791-891-6, S2CID   5254186.
• Луна, JW; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал, 3: 23–28, DOI : 10.1007 / BF02760024, MR   0182577, S2CID   9855414.
• Стикс, В. (2004), "Поиск всех максимальных клик в динамических графах", Computational Optimization Appl., 27 (2): 173-186, CiteSeerX   10.1.1.497.6424, DOI : 10,1023 / Б: COAP.0000008651.28952.b6, S2CID   17824282
• Tomita, E.; Tanaka, A.; Такахаши, Х. (2006), «Наихудшая временная сложность для генерации всех максимальных клик и вычислительных экспериментов», Теоретическая информатика, 363 (1): 28–42, doi : 10.1016 / j.tcs.2006.06.015.
• Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Сиракава, И. (1977), «Новый алгоритм для генерации всех максимальных независимых множеств», SIAM Journal on Computing, 6 (3): 505–517, doi : 10,1137 / 0206036.
• Weigt, Мартин; Хартманн, Александр К. (2001), "Минимальные вершинные покрытия на случайных графах с конечной связностью: картина решеточного газа твердых сфер", Phys. Rev. E, 63 (5): 056127, arXiv : cond-mat / 0011446, Bibcode : 2001PhRvE..63e6127W, doi : 10.1103 / PhysRevE.63.056127, PMID   11414981, S2CID   16773685.
• Yu, C.-W.; Чен, Г.-Х. (1993), «Сгенерировать все максимальные независимые множества в графах перестановок», Междунар. J. Comput. Математика., 47 (1-2): 1-8, DOI : 10,1080 / 00207169308804157.