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

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

Граф куба имеет шесть различных независимых множеств (два из них максимальные), показанных в виде красных вершин.

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

Например, в графе P ₃ , пути с тремя вершинами a , b , и c , и двумя ребрами ab и bc , множества { b } и { a , c } оба максимально независимы. Множество { a } независимо, но не является максимально независимым, потому что оно является подмножеством большего независимого множества { a , c }. В этом же графе максимальными кликами являются множества { a , b } и { b , c }.

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

Два верхних графика P ₃ — это максимальные независимые множества, а два нижних — это независимые множества, но не максимальные. Максимальное независимое множество представлено в верхнем левом углу.

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

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

Два независимых множества для звездного графа S ₈ показывают, насколько сильно могут различаться по размеру два максимальных независимых множества (правое из них является максимальным).

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

Определение

Для графа независимое множество является максимальным независимым множеством , если для выполняется одно из следующих условий: ^[1] ${\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}}$

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

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

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

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

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

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

Мун и Мозер (1965) показали, что любой граф с n вершинами имеет не более 3 n ^/ 3 максимальных клик. Дополнительно, любой граф с n вершинами также имеет не более 3 ⁿ /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}}}.}$

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

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

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

Нахождение единственного максимального независимого множества

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

Для графа G(V,E) легко найти одну MIS, используя следующий алгоритм:

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

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

Следующий алгоритм находит MIS за время O(log n ). ^{[1] [7] [8]}

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

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

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

• По крайней мере 1/2 всех ребер всегда хорошие. ДОКАЗАТЕЛЬСТВО: Постройте направленную версию G, направляя каждое ребро к узлу с более высокой степенью (разрывая связи произвольно). Таким образом, для каждого плохого узла число исходящих ребер более чем в 2 раза превышает число входящих ребер. Таким образом, каждое плохое ребро, которое входит в узел v, может быть сопоставлено с отдельным набором из двух ребер, которые выходят из узла v. Следовательно, общее число ребер по крайней мере в 2 раза превышает число плохих ребер.
• Для каждого хорошего узла u вероятность того, что сосед u будет выбран в S, составляет по крайней мере некоторую положительную константу. ДОКАЗАТЕЛЬСТВО: вероятность того, что НИ ОДИН сосед u не будет выбран в S, составляет не более вероятности того, что не будет выбран ни один из нижних соседей u . Для каждого нижнего соседа v вероятность того, что он не будет выбран, составляет (1-1/2d(v)), что не более (1-1/2d(u)) (так как d(u)>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)>d(u)). По объединению вероятность того, что не будет выбран ни один более высокий сосед, не превышает d(u)/2d(u) = 1/2.
• Следовательно, для каждого хорошего узла u вероятность того, что сосед u будет выбран в S и останется в S, является некоторой положительной константой. Следовательно, вероятность того, что u будет удален на каждом шаге, является по крайней мере положительной константой.
• Следовательно, для каждого хорошего ребра e вероятность того, что e будет удалено на каждом шаге, является по крайней мере положительной константой. Таким образом, количество хороших ребер уменьшается по крайней мере на постоянный множитель на каждом шаге.
• Поскольку по крайней мере половина ребер являются хорошими, общее количество ребер также уменьшается на постоянный коэффициент с каждым шагом.
• Следовательно, количество шагов равно O(log m ), где m — количество ребер. Оно ограничено . ${\displaystyle O(\log(n))}$

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

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

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

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

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

АНАЛИЗ :

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

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

Вместо рандомизации на каждом шаге можно рандомизировать один раз, в начале алгоритма, зафиксировав случайный порядок узлов. Учитывая этот фиксированный порядок, следующий параллельный алгоритм достигает точно такой же MIS, как и алгоритм #Sequential (т.е. результат детерминирован): ^[10]

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

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

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

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

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

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

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

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

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

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

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

Однако эта проблема разрешима на некоторых конкретных классах графов, например, на кографах . ^[16]

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

История

Первоначально считалось, что задача максимального независимого множества нетривиальна для параллелизации из-за того, что лексикографическое максимальное независимое множество оказалось P-полным ; однако было показано, что детерминированное параллельное решение может быть получено путем сведения либо из задачи упаковки максимального множества , либо из задачи максимального соответствия , либо путем сведения из задачи 2-выполнимости . ^{[17] [18]} Как правило, структура приведенного алгоритма следует другим параллельным графовым алгоритмам — то есть они подразделяют граф на более мелкие локальные задачи, которые решаются параллельно путем запуска идентичного алгоритма. ${\displaystyle NC^{1}}$ ${\displaystyle NC^{2}}$

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

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

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

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

Распределенные алгоритмы максимального независимого множества находятся под сильным влиянием алгоритмов на модели PRAM. Оригинальная работа Luby и Alon et al. привела к нескольким распределенным алгоритмам. ^{[21] [22] [23] [20]} С точки зрения обмена битами эти алгоритмы имели нижнюю границу размера сообщения на раунд битов и требовали дополнительных характеристик графа. Например, размер графа должен быть известен или максимальная степень соседних вершин для заданной вершины могла быть запрошена. В 2010 году Métivier et al. уменьшили требуемый размер сообщения на раунд до , что является оптимальным и устраняет необходимость в каких-либо дополнительных знаниях графа. ^[24] ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$

Сноски

1. Эрдёш (1966) показывает, что число различных размеров МИС в графе с n вершинами может достигать n – log n – O (log log n ) и никогда не превышает n – log n .

Примечания

1. Алгоритм Луби, в: Заметки лекций по рандомизированным алгоритмам, последнее обновление Эрика Вигоды 2 февраля 2006 г.
2. Вайгт и Хартманн (2001).
3. Информационная система по включениям классов графов: максимальные кликовые неприводимые графы. Архивировано 09.07.2007 на Wayback Machine и наследственные максимальные кликовые неприводимые графы. Архивировано 08.07.2007 на Wayback Machine .
4. Бысков (2003). Для более ранних результатов см. Croitoru (1979) и Eppstein (2003).
5. Чиба и Нишизеки (1985). Чиба и Нишизеки выражают условие наличия O( n ) ребер эквивалентно, в терминах древовидности графов в семействе, которая является постоянной.
6. Бисдорф и Маричал (2008); Эйлер (2005); Фюреди (1987).
7. Luby, M. (1986). «Простой параллельный алгоритм для задачи максимального независимого множества». SIAM Journal on Computing . 15 (4): 1036–1053. CiteSeerX  10.1.1.225.5475 . doi :10.1137/0215074.
8. "Принципы распределенных вычислений (лекция 7)" (PDF) . ETH Zurich. Архивировано из оригинала (PDF) 21 февраля 2015 г. Получено 21 февраля 2015 г.
9. Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. (2010). «Оптимальный битовый алгоритм рандомизированной распределенной MIS». Distributed Computing . 23 (5–6): 331. doi :10.1007/s00446-010-0121-5. S2CID  36720853.
10. Блеллок, Гай; Файнман, Джереми; Шун, Джулиан (2012). «Жадный последовательный максимальный независимый набор и сопоставление в среднем параллельны». arXiv : 1202.3205 [cs.DS].
11. Эппштейн (2003); Бысков (2003).
12. Эппштейн (2003). Для оценки соответствия широко используемому алгоритму Брона–Кербоша см. Томита, Танака и Такахаши (2006).
13. Бомзе и др. (1999); Эппштейн (2005); Дженнингс и Мотыцкова (1992); Джонсон, Яннакакис и Пападимитриу (1988); Лоулер, Ленстра и Риннуй Кан (1980); Лян, Дхалл и Лакшмиварахан (1991); Макино и Уно (2004); Мишра и Питт (1997); Стикс (2004); Цукияма и др. (1977); Ю и Чен (1993).
14. Макино и Уно (2004); Эппштейн (2005).
15. Прован, Дж. Скотт; Болл, Майкл О. (ноябрь 1983 г.). «Сложность подсчета разрезов и вычисления вероятности связности графа». Журнал SIAM по вычислениям . 12 (4): 777–788. doi :10.1137/0212053. ISSN  0097-5397.
16. Корнейл, Д. Г.; Лерчс, Х.; Берлингхэм, Л. Стюарт (1981-07-01). «Дополнительные сводимые графы». Дискретная прикладная математика . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5. ISSN  0166-218X.
17. Кук, Стивен (июнь 1983 г.). «Обзор вычислительной сложности». Commun. ACM . 26 (6): 400–408. doi : 10.1145/358141.358144 . S2CID  14323396.
18. Barba, Luis (октябрь 2012 г.). "ОБЗОР ЛИТЕРАТУРЫ: Параллельные алгоритмы для задачи максимального независимого множества в графах" (PDF) .
19. Карп, Р. М.; Вигдерсон, А. (1984). «Быстрый параллельный алгоритм для задачи максимального независимого множества». Труды 16-го симпозиума ACM по теории вычислений .
20. Алон, Нога; Ласло, Бабай; Алон, Итай (1986). «Быстрый и простой рандомизированный параллельный алгоритм для задачи максимального независимого множества». Журнал алгоритмов . 7 (4): 567–583. doi :10.1016/0196-6774(86)90019-2.
21. Пелег, Дэвид (2000). Распределенные вычисления: подход, чувствительный к локальности . doi : 10.1137/1.9780898719772. ISBN 978-0-89871-464-7.
22. Линч, NA (1996). «Распределенные алгоритмы». Морган Кауфманн .
23. Ваттенхофер, Р. «Глава 4: Максимальное независимое множество» (PDF) .
24. Метивье, И.; Робсон, Дж. М.; Сахеб-Джахроми, Н.; Земмари, А. (2010). «Распределенный алгоритм MIS с оптимальной битовой сложностью с рандомизацией». Распределенные вычисления .

Ссылки

• Бисдорф, Раймонд; Маришаль, Жан-Люк (2008), «Подсчет неизоморфных максимальных независимых множеств графа n-циклов», Journal of Integer Sequences , 11 : 08.5.7, arXiv : math.CO/0701647.
• Бомзе, ИМ; Будинич, М.; Пардалос, ПМ; Пелильо, М. (1999), «Проблема максимальной клики», Справочник по комбинаторной оптимизации , т. 4, Kluwer Academic Publishers, стр. 1–74, CiteSeerX  10.1.1.48.4074.
• Бысков, Дж. М. (2003), «Алгоритмы для k -раскраски и поиска максимальных независимых множеств», Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Soda '03, стр. 456–457, ISBN 9780898715385.
• Чиба, Н.; Нишизеки, Т. (1985), «Алгоритмы древовидности и перечисления подграфов», SIAM Journal on Computing , 14 (1): 210–223, doi :10.1137/0214017, S2CID  207051803.
• Кроитору, К. (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), «Все максимальные независимые множества и динамическое доминирование для разреженных графов», Труды Шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , т. 5, стр. 451–459, arXiv : cs.DS/0407036 , doi :10.1145/1597036.1597042, S2CID  2769046.
• Эрдёш, П. (1966), «О кликах в графах», Israel Journal of Mathematics , 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.
• Дженнингс, Э.; Мотычкова, Л. (1992), «Распределенный алгоритм поиска всех максимальных клик в сетевом графе», Труды Первого латиноамериканского симпозиума по теоретической информатике , Lecture Notes in Computer Science, т. 583, Springer-Verlag, стр. 281–293
• Джонсон, Д.С.; Яннакакис , М.; Пападимитриу , Ч.Х. (1988), «О генерации всех максимальных независимых множеств», Information Processing Letters , 27 (3): 119–123, doi :10.1016/0020-0190(88)90065-8.
• Лоулер, Э. Л. (1976), «Заметка о сложности проблемы хроматического числа», Information Processing Letters , 5 (3): 66–67, doi :10.1016/0020-0190(76)90065-X.
• Лоулер, Э. Л .; Ленстра, Дж. К .; Ринной Кан, А. Х. Г. (1980), «Генерация всех максимальных независимых множеств: алгоритмы NP-сложности и полиномиального времени» (PDF) , SIAM Journal on Computing , 9 (3): 558–565, doi :10.1137/0209042, S2CID  29527771.
• Leung, JY-T. (1984), «Быстрые алгоритмы для генерации всех максимальных независимых наборов интервальных, дуговых и хордовых графов», Журнал алгоритмов , 5 : 22–35, doi :10.1016/0196-6774(84)90037-3.
• Лян, Й. Д.; Дхалл, С. К.; Лакшмиварахан, С. (1991), «О проблеме нахождения всех независимых множеств максимального веса в интервальных и дуговых графах», Труды симпозиума по прикладным вычислениям 1991 г. , стр. 465–470, doi :10.1109/SOAC.1991.143921, ISBN 0-8186-2136-2, S2CID  122685841
• Макино, К.; Уно, Т. (2004), "Новые алгоритмы для перечисления всех максимальных клик", Труды Девятого скандинавского семинара по теории алгоритмов , Lecture Notes in Computer Science, т. 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 . 
• Мишра, Н.; Питт, Л. (1997), "Генерация всех максимальных независимых множеств гиперграфов ограниченной степени", Труды Десятой конференции по теории вычислительного обучения , стр. 211–217, doi :10.1145/267460.267500, ISBN 978-0-89791-891-6, S2CID  5254186.
• Moon, JW; Moser, L. (1965), «О кликах в графах», Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR  0182577, S2CID  9855414.
• Стикс, В. (2004), «Нахождение всех максимальных клик в динамических графах», Computational Optimization and Applications , 27 (2): 173–186, CiteSeerX  10.1.1.497.6424 , doi :10.1023/B:COAP.0000008651.28952.b6, S2CID  17824282
• Томита, Э.; Танака, А.; Такахаши, Х. (2006), «Сложность времени в худшем случае для генерации всех максимальных клик и вычислительные эксперименты», Теоретическая информатика , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015.
• Цукияма, С.; Иде, М.; Ариёси, Х.; Сиракава, И. (1977), «Новый алгоритм для генерации всех максимальных независимых множеств», SIAM Journal on Computing , 6 (3): 505–517, doi :10.1137/0206036.
• Weigt, Martin; Hartmann, Alexander K. (2001), "Минимальные вершинные покрытия на случайных графах с конечной связностью: картина решеточного газа в виде твердой сферы", Phys. Rev. E , 63 (5): 056127, arXiv : cond-mat/0011446 , Bibcode : 2001PhRvE..63e6127W, doi : 10.1103/PhysRevE.63.056127, PMID  11414981, S2CID  16773685.
• Ю, Ч.-В.; Чен, Г.-Х. (1993), «Сгенерировать все максимальные независимые множества в графах перестановок», Internat. J. Comput. Math. , 47 (1–2): 1–8, doi :10.1080/00207169308804157.