Алгоритм Каргерса - Kargers algorithm

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

В Информатика и теория графов, Алгоритм Каргера это рандомизированный алгоритм вычислить минимальный разрез связанного график. Это было изобретено Дэвид Каргер и впервые опубликовано в 1993 году.^[1]

Идея алгоритма основана на концепции сжатие края ${\displaystyle (u,v)}$ в неориентированном графе ${\displaystyle G=(V,E)}$. Неформально говоря, сжатие ребра объединяет узлы ${\displaystyle u}$ и ${\displaystyle v}$ в один, уменьшив общее количество узлов графа на единицу. Все остальные кромки, соединяющиеся либо ${\displaystyle u}$ или же ${\displaystyle v}$ "присоединяются" к объединенному узлу, эффективно создавая мультиграф. Базовый алгоритм Каргера итеративно сжимает случайно выбранные ребра, пока не останется только два узла; эти узлы представляют собой резать в исходном графике. Повторяя этот базовый алгоритм достаточное количество раз, можно с высокой вероятностью найти минимальный разрез.

Проблема глобального минимума сокращения

Основная статья: Минимальный срез

А резать ${\displaystyle (S,T)}$ в неориентированном графе ${\displaystyle G=(V,E)}$ является разбиением вершин ${\displaystyle V}$ на два непустых непересекающихся множества ${\displaystyle S\cup T=V}$. В Cutset реза состоит из краев ${\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}$ между двумя частями. размер (или же масса) разреза в невзвешенном графе - это мощность разреза, то есть количество ребер между двумя частями,

${\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}$

Есть ${\displaystyle 2^{|V|}}$ способы выбора для каждой вершины, принадлежит ли она ${\displaystyle S}$ или чтобы ${\displaystyle T}$, но два из этих вариантов делают ${\displaystyle S}$ или же ${\displaystyle T}$ пустые и не вызывают порезов. Среди оставшихся вариантов - поменять ролями ${\displaystyle S}$ и ${\displaystyle T}$ не меняет разрез, поэтому каждый разрез учитывается дважды; поэтому есть ${\displaystyle 2^{|V|-1}-1}$ отчетливые разрезы. минимальная проблема среза - найти среди этих разрезов разрез наименьшего размера.

Для взвешенных графов с положительным весом ребер ${\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}$ вес разреза - это сумма весов ребер между вершинами в каждой части

${\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}$

что согласуется с невзвешенным определением для ${\displaystyle w=1}$.

Разрез иногда называют «глобальным разрезом», чтобы отличать его от «${\displaystyle s}$-${\displaystyle t}$ вырезать »для данной пары вершин, что имеет дополнительное требование, чтобы ${\displaystyle s\in S}$ и ${\displaystyle t\in T}$. Каждый глобальный разрез - это ${\displaystyle s}$-${\displaystyle t}$ вырезать для некоторых ${\displaystyle s,t\in V}$. Таким образом, задача минимального разреза может быть решена за полиномиальное время путем перебора всех вариантов ${\displaystyle s,t\in V}$ и решая полученный минимум ${\displaystyle s}$-${\displaystyle t}$ решить проблему с помощью теорема о максимальном потоке и минимальном отсечении и алгоритм полиномиального времени для максимальный поток, такой как алгоритм push-relabel, хотя такой подход не оптимален. Лучшие детерминированные алгоритмы для задачи глобального минимума разреза включают Алгоритм Стоера – Вагнера, который имеет время работы ${\displaystyle O(mn+n^{2}\log n)}$.^[2]

Алгоритм сокращения

Фундаментальная операция алгоритма Каргера представляет собой форму сжатие края. Результат стягивания края ${\displaystyle e=\{u,v\}}$ новый узел ${\displaystyle uv}$. Каждый край ${\displaystyle \{w,u\}}$ или же ${\displaystyle \{w,v\}}$ за ${\displaystyle w\notin \{u,v\}}$ к концам сжатого ребра заменяется ребром ${\displaystyle \{w,uv\}}$ к новому узлу. Наконец, суженные узлы ${\displaystyle u}$ и ${\displaystyle v}$ со всеми их инцидентными ребрами удаляются. В частности, полученный граф не содержит петель. Результат сужения края ${\displaystyle e}$ обозначается ${\displaystyle G/e}$.

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

Успешный запуск алгоритма Каргера на 10-вершинном графе. Минимальный крой имеет размер 3.

   процедура договор(${\displaystyle G=(V,E)}$):   пока ${\displaystyle |V|>2}$       выберите ${\displaystyle e\in E}$ равномерно случайно ${\displaystyle G\leftarrow G/e}$   возвращаться единственный врезанный ${\displaystyle G}$

Когда график представлен с использованием списки смежности или матрица смежности, операция сжатия одной кромки может быть реализована с линейным числом обновлений в структуре данных для общего времени выполнения ${\displaystyle O(|V|^{2})}$. В качестве альтернативы процедуру можно рассматривать как выполнение Алгоритм Краскала для строительства минимальное остовное дерево в графе, у ребер которого есть веса ${\displaystyle w(e_{i})=\pi (i)}$ согласно случайной перестановке ${\displaystyle \pi }$. Удаление самого тяжелого края этого дерева приводит к двум компонентам, описывающим разрез. Таким образом, процедура сокращения может быть реализована как Алгоритм Краскала во время ${\displaystyle O(|E|\log |E|)}$.

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

Наиболее известные реализации используют ${\displaystyle O(|E|)}$ время и пространство, или ${\displaystyle O(|E|\log |E|)}$ время и ${\displaystyle O(|V|)}$ пространство соответственно.^[1]

Вероятность успеха алгоритма сокращения

В графике ${\displaystyle G=(V,E)}$ с ${\displaystyle n=|V|}$ вершин, алгоритм сжатия возвращает минимальный разрез с полиномиально малой вероятностью ${\displaystyle {\binom {n}{2}}^{-1}}$. Каждый граф имеет ${\displaystyle 2^{n-1}-1}$ порезы^[3] среди которых самое большее ${\displaystyle {\tbinom {n}{2}}}$ можно минимальные порезы. Следовательно, вероятность успеха для этого алгоритма намного лучше, чем вероятность случайного выбора разреза, которая не превышает ${\displaystyle {\tbinom {n}{2}}/(2^{n-1}-1)}$

Например, график цикла на ${\displaystyle n}$ вершин ровно ${\displaystyle {\binom {n}{2}}}$ минимальные разрезы, задаваемые каждым выбором из 2 кромок. Процедура сжатия находит каждый из них с равной вероятностью.

Чтобы установить оценку вероятности успеха в целом, пусть ${\displaystyle C}$ обозначают края определенного минимального размера разреза ${\displaystyle k}$. Алгоритм сжатия возвращает ${\displaystyle C}$ если ни одно из случайных ребер не принадлежит сечению ${\displaystyle C}$. В частности, сокращение первого края позволяет избежать ${\displaystyle C}$, что происходит с вероятностью ${\displaystyle 1-k/|E|}$. Минимальная степень ${\displaystyle G}$ по крайней мере ${\displaystyle k}$ (иначе вершина минимальной степени вызовет меньший разрез), поэтому ${\displaystyle |E|\geq nk/2}$. Таким образом, вероятность того, что алгоритм сжатия выберет ребро из ${\displaystyle C}$ является

${\displaystyle {\frac {k}{|E|}}\leq {\frac {k}{nk/2}}={\frac {2}{n}}.}$

Вероятность ${\displaystyle p_{n}}$ что алгоритм сжатия на ${\displaystyle n}$-вершинный граф избегает ${\displaystyle C}$ удовлетворяет повторение ${\displaystyle p_{n}\geq \left(1-{\frac {2}{n}}\right)p_{n-1}}$, с ${\displaystyle p_{2}=1}$, который может быть расширен как

${\displaystyle p_{n}\geq \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}$

Повторение алгоритма сокращения

10 повторов схватки. 5-й повтор находит минимальный разрез размера 3.

Повторяя алгоритм сжатия ${\displaystyle T={\binom {n}{2}}\ln n}$ раз с независимым случайным выбором и возвращением наименьшего разреза, вероятность не найти минимальный разрез составляет

${\displaystyle \left[1-{\binom {n}{2}}^{-1}\right]^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}$

Общее время работы для ${\displaystyle T}$ повторений для графика с ${\displaystyle n}$ вершины и ${\displaystyle m}$ края ${\displaystyle O(Tm)=O(n^{2}m\log n)}$.

Алгоритм Каргера – Стейна

Расширение алгоритма Каргера за счет Дэвид Каргер и Клиффорд Штайн достигает улучшения на порядок.^[4]

Основная идея состоит в том, чтобы выполнять процедуру сжатия, пока график не достигнет ${\displaystyle t}$ вершины.

   процедура договор(${\displaystyle G=(V,E)}$, ${\displaystyle t}$):   пока ${\displaystyle |V|>t}$       выберите ${\displaystyle e\in E}$ равномерно случайно ${\displaystyle G\leftarrow G/e}$   возвращаться ${\displaystyle G}$

Вероятность ${\displaystyle p_{n,t}}$ что эта процедура сокращения позволяет избежать определенного разреза ${\displaystyle C}$ в ${\displaystyle n}$-вершинный граф

${\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}$

Это выражение приблизительно ${\displaystyle t^{2}/n^{2}}$ и становится меньше чем ${\displaystyle {\frac {1}{2}}}$ вокруг ${\displaystyle t=n/{\sqrt {2}}}$. В частности, вероятность того, что ребро из ${\displaystyle C}$ сокращается, растет к концу. Это мотивирует идею перехода на более медленный алгоритм после определенного количества шагов сокращения.

   процедура fastmincut (${\displaystyle G=(V,E)}$):   если ${\displaystyle |V|\leq 6}$:       возвращаться mincut (${\displaystyle V}$)   еще:       ${\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }$       ${\displaystyle G_{1}\leftarrow }$ договор(${\displaystyle G}$, ${\displaystyle t}$)       ${\displaystyle G_{2}\leftarrow }$ договор(${\displaystyle G}$, ${\displaystyle t}$)       возвращаться мин {fastmincut (${\displaystyle G_{1}}$), fastmincut (${\displaystyle G_{2}}$)}

Анализ

Вероятность ${\displaystyle P(n)}$ алгоритм находит конкретное сечение ${\displaystyle C}$ задается рекуррентным соотношением

${\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}$

с раствором ${\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}$. Время работы fastmincut удовлетворяет

${\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}$

с раствором ${\displaystyle T(n)=O(n^{2}\log n)}$. Для достижения вероятности ошибки ${\displaystyle O(1/n)}$, алгоритм можно повторить ${\displaystyle O(\log n/P(n))}$ раз, для общего времени работы ${\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}$. Это улучшение на порядок по сравнению с исходным алгоритмом Каргера.

Граница улучшения

Чтобы определить минимальный разрез, нужно коснуться каждого ребра в графе хотя бы один раз, т.е. ${\displaystyle \Theta (n^{2})}$ время в плотный граф. Алгоритм min-cut Каргера – Стейна занимает время выполнения ${\displaystyle O(n^{2}\ln ^{O(1)}n)}$, что очень близко к этому.

Рекомендации

1. Каргер, Дэвид (1993). «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма сокращения». Proc. 4-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам.
2. Stoer, M .; Вагнер, Ф. (1997). «Простой алгоритм min-cut». Журнал ACM. 44 (4): 585. Дои:10.1145/263867.263872.
3. Патриньяни, Маурицио; Пиццония, Маурицио (2001), «Сложность проблемы сопоставления и сокращения», в Брандштадт, Андреас; Ле, Ван Банг (ред.), Теоретико-графические концепции в компьютерных науках: 27-й международный семинар, WG 2001, Больтенхаген, Германия, 14-16 июня 2001 г., Труды, Конспект лекций по информатике, 2204, Берлин: Springer, стр. 284–295, Дои:10.1007/3-540-45477-2_26, МИСТЕР  1905640.
4. Каргер, Дэвид Р.; Штейн, Клиффорд (1996). «Новый подход к проблеме минимального сокращения» (PDF). Журнал ACM. 43 (4): 601. Дои:10.1145/234533.234534.