Минимальная бисекция: различия между версиями

В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали аппроксимационный алгоритм по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего аппроксимационного алгоритма со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый аппроксимационный алгоритм с полиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом.

(Аппроксимационный алгоритм по двум критериям разбивает вершины на два множества, каждое из которых содержит не более 2/3 вершин, и его значение (т. е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера).

Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим <math>\bar{S} = V \backslash S \;</math>. [[Разрез]] <math>(\bar{S}, S) \;</math>, также называемый [[сечение|сечением]], определяется как множество всех ребер, имеющих одну конечную точку в <math>S \;</math>, а другую – в <math>\bar{S} \;</math>. Говорится, что эти ребра пересекают разрез, а множества <math>S \;</math> и <math>\bar{S} \;</math> называются сторонами разреза.

Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). [[Стоимость]] разреза <math>(S, \bar{S}) \;</math> определяется как сумма весов всех ребер, пересекающих разрез.

Разрез (S, S’) называется [[бисекция|бисекцией]] графа G, если обе его стороны имеют одинаковую мощность, а именно – <math>|S| = |\bar{S}| = n/2 \;</math>. Обозначим за b(G) минимальную стоимость бисекции G.

'''Задача 1 (Минимальная бисекция)'''

Требуется: найти бисекцию <math>(S, \bar{S}) \;</math> графа G с минимальной стоимостью.

Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [10] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [9], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время.

== Сбалансированные разрезы и реберные сепараторы ==

Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для <math>0 < \beta < 1 \;</math> разрез <math>(S, \bar{S}) \;</math> называется <math>\beta</math>-сбалансированным, если <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>. Отметим, что из последнего требования следует <math>min \{ |S|, |\bar{S}| \} \ge (1 - \beta) n \;</math>. В этих терминах бисекция является 1/2-сбалансированным разрезом.

'''Задача 2 (<math>\beta</math>-сбалансированный разрез)'''

Требуется: найти <math>\beta</math>-сбалансированный разрез <math>(S, \bar{S}) \;</math> графа G с <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>, такой, что его стоимость насколько возможно мала.

Специальный случай <math>\beta = 2/3 \;</math> часто называется задачей о реберном сепараторе (EDGE-SEPARATOR).

В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза <math>(S, \bar{S}) \;</math>, такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число <math>r \ge 2 \;</math> – или разделить граф на r фрагментов размерами <math>k_1, ..., k_r \;</math>, где числа <math>k_i \;</math> заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами.

'''Задача 3. Заранее заданное разбиение'''

Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа <math>k_1, ..., k_r \;</math>, такие, что <math>\sum_i k_i = |V| \;</math>.

Фейге и Краутхамер [6] предложили аппроксимационный алгоритм для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации <math>O(log^2 \; n)</math>, поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до <math>O(log^{1,5} \; n)</math>.

'''Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>. Более конкретно, алгоритм создает для входного графа G бисекцию <math>(S, \bar{S}) \;</math>, стоимость которой не превышает <math>O(log^{1,5} \; n) \cdot b(G)</math>.'''

'''Теорема 2. Задача о <math>\beta</math>-сбалансированном разрезе (и, в частности, о реберном сепараторе) может быть приближенно решена за полиномиальное время с коэффициентом <math>O(log^{1,5} \; n)</math>.'''

'''Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время <math>n^{O(r)} \;</math> с коэффициентом <math>O(log^{1,5} \; n)</math>.'''

'''Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, <math>\beta</math>-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).'''

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM Review 48(1), 99-130 (2006) (Previous versions appeared in Proceedings of 41st FOCS, 1999; and in SIAM J. Comput. 2002)

 

 

10. Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46-76 (2000)

 

11. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291-307 (1970)

 

 

13. Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing, pp. 682-690, San Diego, 1993 May 16-18

 

 

15. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615-627 (1980)

17. Svitkina, Z., Tardos, Ё.: Min-Max multiway cut. In: 7th International workshop on Approximation algorithms for combinatorial optimization (APPROX), pp. 207-218, Cambridge, 2004 August 22-24