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

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

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

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

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

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

В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза (S, S), такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число r > 2 – или разделить граф на r фрагментов размерами k1,... , kr, где числа ki заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами.

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

Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа k1, ... , kr, такие, что Pi ki = j Vj.

Требуется: найти разбиение V = V 1 • • • U Vr графа G с j V i j = ki для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам Vi, насколько возможно мал.

Основные результаты

Фейге и Краутхамер [ ] предложили алгоритм аппроксимации для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации O(log 2n), поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [ ], авторы улучшили коэффициент до O(log ' и).

Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n). Более конкретно, алгоритм создает для входного графа G бисекцию (S, S), стоимость которой не превышает O(log1:5 n) ■ b(G).

Алгоритм можно непосредственно расширить на родственные или более общие задачи с получением сходных результатов.

Теорема 2. Задача о сбалансированном разрезе (и, в частности, о реберном сепараторе может быть приближенно решена за полиномиальное время с коэффициентом O(log1:5 n).

Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время nO(r) с коэффициентом O(log1:5 n).

Для всех трех вышеприведенных задач коэффициент аппроксимации можно улучшить до O(log n) для семейства графов, не включающих фиксированный минор (в частности, сюда входят некоторые планарные графы). Для простоты здесь приводятся результаты для задачи о минимальной бисекции.

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

Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [ 6].

Родственные работы

Алгоритм аппроксимации по двум критериям для нахождения f$-сбалансированного разреза возвращает разрез, являющийся /^'-сбалансированным для заранее определенного значения /}' > p. Например, для бисекции, P = 1/2; обычно P' = 2/3.

Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого неплотного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом O(log n) для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти алгоритмы аппроксимации для вычисления разреза с минимальным частным позволяют получить алгоритм аппроксимации по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более O(logn) • b(G). Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как b(G) = Q(n2). Информацию о других работах в этом направлении, включая алгоритмы аппроксимации для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [ ] и по ссылкам, приведенным в этой работе.

Применение

Важной областью применения для задачи о минимальной бисекции и других задач о разбиении графов является подход «разделяй и властвуй» к решению множества задач оптимизации, особенно на графах – см., например, [15, 16]. Эти задачи естественным образом возникают в разнообразных практических ситуациях – таких как проектирование СБИС и обработка изображений – а также в других сферах, например, в качестве задач кластеризации.

Кроме того, алгоритм минимальной бисекции находит широкое применение в задачах задачах и распределении – в форме, общей для параллельных систем и научных вычислений: необходимо назначать компьютерам задания максимально сбалансированным образом, стараяь присвоить как можно больше определенных фрагментов задания одному компьютеру. Например, рассмотрим ситуацию с назначением n заданий двум компьютерам, для которой известен объем коммуникаций между каждыми двумя заданиями, а цель заключается в обеспечении обоим компьютерам равной нагрузки (количества заданий) и сведения к минимуу количества коммуникаций между компьютерами. Очевидно, что эту задачу можно сформулировать как задачу о минимальной бисекции в подходящим образом сформированном графе.

Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) алгоритм аппроксимации для решения задачи о минимальной бисекции в k-однородных гиперграфах [ ]; (2) алгоритм аппроксимации для варианта задачи о минимальном множественном разрезе [ ]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5].

С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найтив [ ]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11].

Открытые вопросы

В настоящее время существует большой разрыв между коэффициентом аппроксимации O(log n) для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9].

Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения e > 0 задача аппроксимации минимальной бисекции с дополнительным членом и2~е будет NP-полной. Фейге [ ] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения " > 0 не существует алгоритма 4/3-аппроксимации задачи о минимальной бисекции. Хот [ ] доказал, что для нахождения минимальной бисекции неприменима схема аппроксимации с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения.

Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – наприме, при помощи алгоритма из [2], применив его вне подхода «черного ящика».