Минимальная бисекция
Ключевые слова и синонимы
Постановка задачи
Минимальная бисекция – это базовое представление семейства задач дискретной оптимизации, имеющих дело с разбиением вершин входного графа. Обычно цель заключается в минимизации количества ребер, соединяющих два отдельных фрагмента графа, при сохранении некоторого контроля над разбиением – например,за счет ограничения количества и/или размера фрагментов. (Это описание соответствует реберному разрезу графа; в случае вершинного разреза употребляются схожие ограничение). Целью задачи о минимальной бисекции является разбиение вершин входного графа на два множества равного размера, такое, чтобы количество ребер, соединяющих эти два множества, было насколько возможно малым.
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали алгоритм аппроксимации по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего алгоритма аппроксимации со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый алгоритм аппроксимации солиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом.
(Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера).
Разрезы и бисекции
Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим S = V n S. Разрез (S, S’), также называемый сечением, определяется как множество всех ребер, имеющих одну конечную точку в S, а другую – в S’. Говорится, что эти ребра пересекают разрез, а множества S и S’ называются сторонами разреза.
Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагатьвеса всех ребер единичными). Стоимость разреза (S, S’) определяется как сумма весов всех ребер, пересекающих разрез.
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = |S’| = n/2. Обозначим за b(G) минимальную стоимость бисекции G.
Задача 1 (Минимальная бисекция)
Дано: неориентированный граф G с неотрицательными весами ребер.
Требуется: найти бисекцию (S, S) графа G с минимальной стоимостью.
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время.
Сбалансированные разрезы и реберные сепараторы
Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для 0 < (3 < 1 разрез (S,; S) называется ^-сбалансированным, если maxfjSj; \S\} < fin. Отметим, что из последнего требования следует minfjSj; \S\} > (1 — f$)n. В этих терминах бисекция является 1/2-сбалансированным разрезом.
Задача 2 (/!-сбалансированный разрез)
Дано: неориентированный граф G с неотрицательными весами ребер.
Требуется: найти ft-сбалансированный разрез (S, S) графа G с maxfjSj; \S\} j f$ n, такой, что его стоимость насколько возможно мала.
Специальный случай f$ = 2/3 часто называется задачей о реберном сепараторе (EDGE-SEPARATOR).