Алгори́тм Ка́ргера ( англ. Karger's algorithm ) — в информатике и теории графов является вероятностным алгоритмом , позволяющим найти минимальный разрез связного графа . Алгоритм изобретен (англ.) ( и опубликован в 1993 году .

Идея алгоритма основана на стягивании ребра в неориентированном графе. Во время стягивания ребра происходит объединение двух вершин в одну, что уменьшает количество вершин графа на единицу. Все рёбра стягиваемых вершин соединяются со вновь образованной вершиной, порождая мультиграф . Алгоритм Каргера итеративно выбирает случайные рёбра и выполняет операцию до тех пор, пока не останется две вершины, которые и представляют собой разрез изначального графа. Если повторять алгоритм достаточное количество раз, то с высокой вероятностью может быть найден минимальный разрез.

Описание

Примеры

Основной задачей является поиск узких мест в различных сетях. Примеры:

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

Алгоритм

Основной операцией алгоритма Каргера является одна из форм стягивания ребра . Для выполнения этой операции на произвольном ребре ${\displaystyle e=\{u,v\}}$ происходит объединение вершин графа ${\displaystyle u}$ и ${\displaystyle v}$ в одну ${\displaystyle uv}$ . Если удаляется вершина ${\displaystyle v}$ , то каждое ребро вида ${\displaystyle \{v,x\}}$ заменяется на ребро вида ${\displaystyle \{u,x\}}$ . Петли удаляются, и после этой операции граф не содержит петель. Функция стоимости переопределяется следующим образом: ${\displaystyle c'(e)={\begin{cases}c(e),&u,v\notin e\\c(e),&e=(x,u)\land (x,v)\notin E\\c((x,v)),&e\neq (x,u)\land (x,v)\in E\\c(e)+c((x,v)),&e=(x,u)\land (x,v)\in E\end{cases}}}$ .

Алгоритм представляет собой равновероятный выбор случайного имеющегося ребра и объединение вершин согласно описанной операции. Результатом работы алгоритма является пара вершин, множество рёбер между которыми является разрезом графа. Этот разрез может быть не минимальным, но вероятность того, что этот разрез минимальный существенно больше, чем для случайно выбранного разреза.

Псевдокод

Алгоритм Каргера
повторить n − 2 раза
  выбрать случайно ребро e
  стянуть ребро e
результат число рёбер между двумя последними вершинами

Доказательства

Лемма 1. ${\displaystyle \mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]\geqslant 1-{\frac {2}{n-i+1}}}$ .

Доказательство. Заметим, что каждый разрез в ${\displaystyle H_{j}}$ соответствует разрезу в ${\displaystyle G}$ . Пусть ${\displaystyle k=|K|}$ , ${\displaystyle n_{j}=|V(H_{j})|}$ и ${\displaystyle m_{j}=|E(H_{j})|}$ . Тогда справедливы следующие развенства: ${\displaystyle n_{i-1}=n-i+1}$ , ${\displaystyle m_{i-1}\geqslant k\cdot n_{i-1}/2}$ (при условии что ${\displaystyle k\leqslant \delta (H_{i-1})}$ ) и ${\displaystyle \mathbb {Pr} [e_{i}\in K]={\frac {k}{m_{i-1}}}}$ . Таким образом ${\displaystyle \mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]={\frac {k}{m_{i-1}}}\geqslant {\frac {2}{n_{i-1}}}=1-{\frac {2}{n-i+1}}}$ .

Лемма 2. Вероятность того, что результат работы алгоритма - наименьший разрез, больше или равен ${\displaystyle {\tbinom {n}{2}}^{-1}}$ .

Доказательство. Пусть ${\displaystyle e_{i}}$ - ${\displaystyle i}$ -тое стянутое ребро при условии, что ${\displaystyle 1\leqslant i\leqslant n-2}$ . Далее пусть ${\displaystyle H_{0}=G}$ и ${\displaystyle H_{i}}$ графы после ${\displaystyle i}$ -того стягивания, а ${\displaystyle K}$ - любой наименьший разрез графа ${\displaystyle G}$ . Тогда справедливо следующее:

Алгоритм Каргера-Штайна

Заметим, что вероятность не найти наименьший разрез при ${\displaystyle t\cdot {\tbinom {n}{2}}}$ повторов равна ${\displaystyle (1-{\tbinom {n}{2}}^{-1})^{t\cdot {\tbinom {n}{2}}}\leqslant (1/e)^{t}}$ . Таким образом можно произвольно уменьшать вероятность ошибки, но при этом будет увеличиваться время выполнения алгоритма. Для константой вероятности ошибки достаточно запустить алгоритм ${\displaystyle {\tbinom {n}{2}}}$ раз и время выполнения при этом увеличится до ${\displaystyle O(n^{4})}$ . Как только константная вероятность ошибки будет достигнута, она будет экспоненциально уменьшаться в зависимости от ${\displaystyle t}$ . До сих пор возможные наименьшие разрезы генерировались алгоритмом независимо при каждом вызове, однако результаты первых слияний рёбер можно использовать для многих запусков. Идея алгоритма Каргера-Штайна заключается в том, чтобы определять два кандидата на стягивание каждую итерацию и продолжать работу алгоритма Каргера рекурсивно для каждой из них:

1. Даны ${\displaystyle G=(V,E)}$ и ${\displaystyle c\colon E\to \mathbb {N} ^{+}}$ .
2. Если ${\displaystyle |V|\leqslant 6}$ , найди наименьший разрез ${\displaystyle C_{U}}$ и выведи его, заверши работу.
3. Установи ${\displaystyle t=\lceil 1+{\frac {n}{\sqrt {2}}}\rceil }$ .
4. Установи ${\displaystyle H=H'=G}$ .
5. Стяни ${\displaystyle n-t}$ рёбер в ${\displaystyle H}$ .
6. Стяни ${\displaystyle n-t}$ рёбер в ${\displaystyle H'}$ .
7. Вычисли рекусивно наименьшие разрезы ${\displaystyle C_{H}}$ и ${\displaystyle C_{H'}}$ .
8. Выведи наименьший разрез ${\displaystyle C_{H}}$ или ${\displaystyle C_{H'}}$ .

Теорема. Алгоритм Каргера-Штайна имеет временную сложность ${\displaystyle O(n^{2}\cdot \log n)}$ .

Доказательство. Следующее упрощенное рекурсивное уравнение описывает время работы алгоритма: ${\displaystyle T(n)=2\cdot T(\lceil 1+{\frac {n}{\sqrt {2}}}\rceil )+O(n^{2})}$ для ${\displaystyle n>6}$ и ${\displaystyle T(n)=O(1)}$ для ${\displaystyle n\leqslant 6}$ . Глубина рекурсии равна ${\displaystyle D=O(\log n)}$ , так как размер входных данных уменьшается в константное количество раз. Пусть ${\displaystyle n_{l}=|V(H)|}$ на уровне рекурсии ${\displaystyle l\geqslant 0}$ . Заметим, что на уровне рекурсии ${\displaystyle l}$ необходимо запустить алгоритм ${\displaystyle 2^{l}}$ раз и размер входного графа для каждого рекурсивного вызова равен ${\displaystyle n_{l}\equiv {\frac {n}{({\sqrt {2}})^{l}}}}$ . Таким образом время выполнения каждого рекурсивного вызова ${\displaystyle O(n_{l}^{2})=O({\frac {n^{2}}{2^{l}}})}$ , а время выполнения, необходимое в пределах глубины рекурсии равно ${\displaystyle 2^{l}\cdot O({\frac {n^{2}}{2^{l}}})=O(n^{2})}$ . Общее же время выполнение равно ${\displaystyle O(n^{2}\cdot \log n)}$ .

Лемма. ${\displaystyle p(t)\geqslant {\frac {1}{t+1}}}$ .

Доказательство.

Теорема. Алгоритм вычисляет наименьший разрез с вероятностью ${\displaystyle \Omega (1/\log n)}$ .

Доказательство. Пусть ${\displaystyle K}$ - наименьший разрез в графе и ${\displaystyle k=|K|}$ . Тогда вероятность того, что ${\displaystyle K}$ сохранится после ${\displaystyle n-t}$ стягиваний равна минимум:

Вероятность того, что ${\displaystyle H}$ или ${\displaystyle H'}$ имеют тот же наименьший разрез, что и ${\displaystyle G}$ равна минимум ${\displaystyle {\frac {1}{2}}}$ . Алгоритм Каргера-Штайна завершится успешно только в двух случаях: если ${\displaystyle H}$ или ${\displaystyle H'}$ содержат минимальный разрез размером ${\displaystyle k}$ и рекусивный вызов алгоритма успешен. ПУсть ${\displaystyle P(G')}$ вероятноть того, что алгоритм успешен для графа ${\displaystyle G'}$ . Тогда вероятность того, что алгоритм завершится успешно ${\displaystyle P(G)\geqslant 1-(1-P(H)/2)\cdot (1-P(H')/2)}$ . Пусть ${\displaystyle p(t)}$ - вероятность того, что алгоритм успешен на уровне рекурсии ${\displaystyle t}$ . Тогда действительно ${\displaystyle p(t)\geqslant 1-(1-p(t-1)/2)^{2}}$ если ${\displaystyle t\geqslant 1}$ и ${\displaystyle p(0)=1}$ . Из ${\displaystyle p(t)\geqslant {\frac {1}{t+1}}}$ следует, что ${\displaystyle P(G)=p(D)\geqslant {\frac {1}{D+1}}=\Omega ({\frac {1}{\log n}})}$ , где ${\displaystyle D=O(\log n)}$ - глубина рекурсии.

После перезапуска алгоритма ${\displaystyle O(\log n)}$ раз, получим время выполнения ${\displaystyle O(n^{2}\log ^{2}n)}$ и вероятность ошибки ${\displaystyle \Omega (1)}$ .

См. также

• Алгоритм Штёр — Вагнера

Примечания

Ссылки