Алгоритм Каргера

Алгоритм Каргера
Граф и два его разреза. Красный разрез пересекает три ребра, а зеленый два. Последний является одним из минимальных разрезов данного графа.
Назван в честь	David Karger[d]
Предназначение	поиск наименьшего разреза графа
Структура данных	граф
Среднее время	$O(Tm)=O(n^{2}m\log n)$
Затраты памяти	-

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

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

Описание

Примеры

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

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

Алгоритм

Операция стягивания ребра алгоритма Каргера.

Основной операцией алгоритма Каргера является одна из форм стягивания ребра. Для выполнения этой операции на произвольном ребре $e=\{u,v\}$ происходит объединение вершин графа $u$ и $v$ в одну $uv$. Если удаляется вершина $v$, то каждое ребро вида $\{v,x\}$ заменяется на ребро вида $\{u,x\}$. Петли удаляются, и после этой операции граф не содержит петель. Функция стоимости переопределяется следующим образом: $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}}$.

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

Пример успешной работы алгоритма для графа с 10 вершинами. Минимальный разрез равен трём.

Псевдокод

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

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

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

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

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

${\begin{aligned}\mathbb {Pr} [C{\text{ is a min. Cut}}]&\geqslant \mathbb {Pr} [C=K]\\&=\mathbb {Pr} [\bigcap _{1\leqslant i\leqslant n-2}e_{i}\notin K]\\&=\prod _{1\leqslant i\leqslant n-2}\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]\\&\geqslant \prod _{1\leqslant i\leqslant n-2}(1-{\frac {2}{n-i+1}})\\&=\prod _{1\leqslant i\leqslant n-2}{\frac {n-i-1}{n-i+1}}\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot \dots \cdot {\frac {2}{4}}\cdot {\frac {1}{3}}\\&={\frac {2}{n(n-1)}}={\tbinom {n}{2}}^{-1}\\\end{aligned}}$

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

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

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

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

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

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

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

${\begin{aligned}p(t)&\geqslant 1-(1-p(t-1)/2)^{2}\\&\geqslant 1-(1-{\frac {1}{2t}})^{2}\\&={\frac {1}{t}}-{\frac {1}{4t^{2}}}\\&={\frac {4t-1}{4t^{2}}}\\&={\frac {(4t-1)(t+1)}{4t^{2}}}\cdot {\frac {1}{t+1}}\\&={\frac {4t^{2}+4t-t-1}{4t^{2}}}\cdot {\frac {1}{t+1}}\\&\geqslant {\frac {1}{t+1}}\end{aligned}}$

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

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

${\begin{aligned}\prod _{1\leqslant i\leqslant n-t}(1-{\frac {2}{n-i+1}})&=\prod _{1\leqslant i\leqslant n-t}({\frac {n-i-1}{n-i+1}})\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot \dots \cdot {\frac {t}{t+2}}\cdot {\frac {t-1}{t+1}}\\&={\frac {t(t-1)}{n(n-1)}}\\&={\frac {\lceil 1+n/{\sqrt {2}}\rceil \cdot \lceil n/{\sqrt {2}}\rceil }{n(n-1)}}\\&\geqslant {\frac {1}{2}}\\\end{aligned}}$

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

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

См. также

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

Ссылки

• Илья И. Колыхматов, Антон В. Яковлев Задача о минимальном разрезе