Минимальная бисекция

Ключевые слова и синонимы

Бисекция графа

Постановка задачи

Минимальная бисекция – это базовое представление семейства задач дискретной оптимизации, имеющих дело с разбиением вершин входного графа. Обычно цель заключается в минимизации количества ребер, соединяющих два отдельных фрагмента графа, при сохранении некоторого контроля над разбиением – например,за счет ограничения количества и/или размера фрагментов. (Это описание соответствует реберному разрезу графа; в случае вершинного разреза употребляются схожие ограничение). Целью задачи о минимальной бисекции является разбиение вершин входного графа на два множества равного размера, такое, чтобы количество ребер, соединяющих эти два множества, было насколько возможно малым.

В своей основополагающей статье 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.