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

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

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

Глобальная проблема минимального разреза

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

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

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

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

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

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

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

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

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

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

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

   procedure contract( $G=(V,E)$ ):
   while  $|V|>2$ 
       choose  $e\in E$  uniformly at random
        $G\leftarrow G/e$ 
   return the only cut in  $G$

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

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

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

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

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

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

{\frac {k}{|E|}}\leqslant {\frac {k}{nk/2}}={\frac {2}{n}}.

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

p_{n}\geqslant \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}\,.

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

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

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

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

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

Расширение алгоритма Каргера, предложенное Дэвидом Каргером и Клиффордом Стайном , обеспечивает улучшение на порядок. ^{[ 3 ]}

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

   procedure contract( $G=(V,E)$ ,  $t$ ):
   while  $|V|>t$ 
       choose  $e\in E$  uniformly at random
        $G\leftarrow G/e$ 
   return  $G$

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

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

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

   procedure fastmincut( $G=(V,E)$ ):
   if  $|V|\leq 6$ :
       return contract( $G$ ,  $2$ )
   else:
        $t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil$ 
        $G_{1}\leftarrow$  contract( $G$ ,  $t$ )
        $G_{2}\leftarrow$  contract( $G$ ,  $t$ )
       return min{fastmincut( $G_{1}$ ), fastmincut( $G_{2}$ )}

Анализ

Параметр сокращения $t$ выбирается так, чтобы каждый вызов контракта имел вероятность не менее 1/2 успеха (то есть избежать сжатия ребра из определенного набора разрезов). $C$ ). Это позволяет моделировать успешную часть рекурсивного дерева как случайное двоичное дерево, созданное критическим процессом Гальтона-Ватсона , и соответствующим образом анализировать. ^{[ 3 ]}

Вероятность $P(n)$ что это случайное дерево успешных вызовов содержит достаточно длинный путь, чтобы добраться до базы рекурсии и найти $C$ задается рекуррентным соотношением

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Каргер, Дэвид (1993). «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма Mincut» . Учеб. 4-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам .
^ Стоер, М.; Вагнер, Ф. (1997). «Простой алгоритм минимального сокращения» . Журнал АКМ . 44 (4): 585. дои : 10.1145/263867.263872 . S2CID 15220291 .
^ Jump up to: ^а ^б ^с Каргер, Дэвид Р .; Штейн, Клиффорд (1996). «Новый подход к проблеме минимального разреза» (PDF) . Журнал АКМ . 43 (4): 601. дои : 10.1145/234533.234534 . S2CID 5385337 .

[karger1993-1] Jump up to: ^а ^б Каргер, Дэвид (1993). «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма Mincut» . Учеб. 4-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам .

[simplemincut-2] Стоер, М.; Вагнер, Ф. (1997). «Простой алгоритм минимального сокращения» . Журнал АКМ . 44 (4): 585. дои : 10.1145/263867.263872 . S2CID 15220291 .

[faster-3] Jump up to: ^а ^б ^с Каргер, Дэвид Р .; Штейн, Клиффорд (1996). «Новый подход к проблеме минимального разреза» (PDF) . Журнал АКМ . 43 (4): 601. дои : 10.1145/234533.234534 . S2CID 5385337 .

[ 1 ]

[ 2 ]

[ 3 ]