Минимальная бисекция
Ключевые слова и синонимы
Постановка задачи
Минимальная бисекция – это базовое представление семейства задач дискретной оптимизации, имеющих дело с разбиением вершин входного графа. Обычно цель заключается в минимизации количества ребер, соединяющих два отдельных фрагмента графа, при сохранении некоторого контроля над разбиением – например,за счет ограничения количества и/или размера фрагментов. (Это описание соответствует реберному разрезу графа; в случае вершинного разреза употребляются схожие ограничение). Целью задачи о минимальной бисекции является разбиение вершин входного графа на два множества равного размера, такое, чтобы количество ребер, соединяющих эти два множества, было насколько возможно малым.
В своей основополагающей статье 1988 года Лейтон и Рао [14] разработали аппроксимационный алгоритм по двум критериям для решения задачи о минимальной бисекции с логарифмическим коэффициентом. Этот алгоритм нашел множество приложений, однако вопрос поиска настоящего аппроксимационного алгоритма со схожим коэффициентом оставался открытым еще десять лет. В 1999 году Файге и Краутгамер [6] предложили первый аппроксимационный алгоритм с полиномиальным временем выполнения, который аппроксимирует задачу с полилогарифмическим относительно размера графа коэффициентом.
(Аппроксимационный алгоритм по двум критериям разбивает вершины на два множества, каждое из которых содержит не более 2/3 вершин, и его значение (т. е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера).
Разрезы и бисекции
Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим [math]\displaystyle{ \bar{S} = V \backslash S \; }[/math]. Разрез [math]\displaystyle{ (\bar{S}, S) \; }[/math], также называемый сечением, определяется как множество всех ребер, имеющих одну конечную точку в [math]\displaystyle{ S \; }[/math], а другую – в [math]\displaystyle{ \bar{S} \; }[/math]. Говорится, что эти ребра пересекают разрез, а множества [math]\displaystyle{ S \; }[/math] и [math]\displaystyle{ \bar{S} \; }[/math] называются сторонами разреза.
Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). Стоимость разреза [math]\displaystyle{ (S, \bar{S}) \; }[/math] определяется как сумма весов всех ребер, пересекающих разрез.
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – [math]\displaystyle{ |S| = |\bar{S}| = n/2 \; }[/math]. Обозначим за b(G) минимальную стоимость бисекции G.
Задача 1 (Минимальная бисекция)
Дано: неориентированный граф G с неотрицательными весами ребер.
Требуется: найти бисекцию [math]\displaystyle{ (S, \bar{S}) \; }[/math] графа G с минимальной стоимостью.
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [10] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [9], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время.
Сбалансированные разрезы и реберные сепараторы
Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для [math]\displaystyle{ 0 \lt \beta \lt 1 \; }[/math] разрез [math]\displaystyle{ (S, \bar{S}) \; }[/math] называется [math]\displaystyle{ \beta }[/math]-сбалансированным, если [math]\displaystyle{ max \{ |S|, |\bar{S}| \} \le \beta n \; }[/math]. Отметим, что из последнего требования следует [math]\displaystyle{ min \{ |S|, |\bar{S}| \} \ge (1 - \beta) n \; }[/math]. В этих терминах бисекция является 1/2-сбалансированным разрезом.
Задача 2 ([math]\displaystyle{ \beta }[/math]-сбалансированный разрез)
Дано: неориентированный граф G с неотрицательными весами ребер.
Требуется: найти [math]\displaystyle{ \beta }[/math]-сбалансированный разрез [math]\displaystyle{ (S, \bar{S}) \; }[/math] графа G с [math]\displaystyle{ max \{ |S|, |\bar{S}| \} \le \beta n \; }[/math], такой, что его стоимость насколько возможно мала.
Специальный случай [math]\displaystyle{ \beta = 2/3 \; }[/math] часто называется задачей о реберном сепараторе (EDGE-SEPARATOR).
В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза [math]\displaystyle{ (S, \bar{S}) \; }[/math], такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число [math]\displaystyle{ r \ge 2 \; }[/math] – или разделить граф на r фрагментов размерами [math]\displaystyle{ k_1, ..., k_r \; }[/math], где числа [math]\displaystyle{ k_i \; }[/math] заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами.
Задача 3. Заранее заданное разбиение
Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа [math]\displaystyle{ k_1, ..., k_r \; }[/math], такие, что [math]\displaystyle{ \sum_i k_i = |V| \; }[/math].
Требуется: найти разбиение [math]\displaystyle{ V = V_1 \cup ... \cup V_r \; }[/math] графа G с [math]\displaystyle{ |V_i| = k_i \; }[/math] для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам [math]\displaystyle{ V_i \; }[/math], насколько возможно мал.
Основные результаты
Фейге и Краутхамер [6] предложили аппроксимационный алгоритм для задачи о минимальной бисекции. Изначально они получили коэффициент апрроксимации [math]\displaystyle{ O(log^2 \; n) }[/math], поскольку в их подходе использовался алгоритм Лейтона и Рао [14]; однако, применив вместо него алгоритм из [2], авторы улучшили коэффициент до [math]\displaystyle{ O(log^{1,5} \; n) }[/math].
Теорема 1. Задача о минимальной бисекции может быть приближенно решена за полиномиальное время с коэффициентом [math]\displaystyle{ O(log^{1,5} \; n) }[/math]. Более конкретно, алгоритм создает для входного графа G бисекцию [math]\displaystyle{ (S, \bar{S}) \; }[/math], стоимость которой не превышает [math]\displaystyle{ O(log^{1,5} \; n) \cdot b(G) }[/math].
Алгоритм можно непосредственно расширить на родственные или более общие задачи с получением сходных результатов.
Теорема 2. Задача о [math]\displaystyle{ \beta }[/math]-сбалансированном разрезе (и, в частности, о реберном сепараторе) может быть приближенно решена за полиномиальное время с коэффициентом [math]\displaystyle{ O(log^{1,5} \; n) }[/math].
Теорема 3. Задача о заранее заданном разбиении может быть приближенно решена за время [math]\displaystyle{ n^{O(r)} \; }[/math] с коэффициентом [math]\displaystyle{ O(log^{1,5} \; n) }[/math].
Для всех трех вышеприведенных задач коэффициент аппроксимации можно улучшить до O(log n) для семейства графов, не включающих фиксированный минор (в частности, сюда входят некоторые планарные графы). Для простоты здесь приводятся результаты для задачи о минимальной бисекции.
Теорема 4. Для графов, не включающих фиксированный граф в качестве минора (т.е. планарных графов) задачи о минимальной бисекции, [math]\displaystyle{ \beta }[/math]-сбалансированном сечении и заранее заданном разбиении с фиксированным r могут быть приближенно решены за полиномиальное время с коэффициентом O(log n).
Стоит отметить, что все эти результаты можно еще больше обобщить, включая в них веса вершин и вершины-полюса (пары s — t); см. главу 5 в [6].
Родственные работы
Аппроксимационный алгоритм по двум критериям для нахождения [math]\displaystyle{ \beta }[/math]-сбалансированного разреза возвращает разрез, являющийся [math]\displaystyle{ \beta' }[/math]-сбалансированным для заранее определенного значения [math]\displaystyle{ \beta' \gt \beta \; }[/math]. Например, для бисекции [math]\displaystyle{ \beta = 1/2 \; }[/math] и чаще всего [math]\displaystyle{ \beta' = 2/3 \; }[/math].
Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) аппроксимационный алгоритм для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого разреженного сечения с равномерным спросом (?). Лучшие из известных на данный момент аппроксимационные алгоритмы с коэффициентом [math]\displaystyle{ O( \sqrt{log \; n}) }[/math] для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти аппроксимационные алгоритмы для вычисления разреза с минимальным частным позволяют получить аппроксимационный алгоритм по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более [math]\displaystyle{ O( \sqrt{log \; n}) \cdot b(G) }[/math]. Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как [math]\displaystyle{ b(G) = \Omega(n^2) \; }[/math]. Информацию о других работах в этом направлении, включая аппроксимационные алгоритмы для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [6] и по ссылкам, приведенным в этой работе.
Применение
Важной областью применения для задачи о минимальной бисекции и других задач о разбиении графов является подход «разделяй и властвуй» к решению множества задач оптимизации, особенно на графах – см., например, [15, 16]. Эти задачи естественным образом возникают в разнообразных практических ситуациях – таких как проектирование СБИС и обработка изображений – а также в других сферах, например, в качестве задач кластеризации.
Кроме того, алгоритм минимальной бисекции находит широкое применение в задачах задачах и распределении – в форме, общей для параллельных систем и научных вычислений: необходимо назначать компьютерам задания максимально сбалансированным образом, стараяь присвоить как можно больше определенных фрагментов задания одному компьютеру. Например, рассмотрим ситуацию с назначением n заданий двум компьютерам, для которой известен объем коммуникаций между каждыми двумя заданиями, а цель заключается в обеспечении обоим компьютерам равной нагрузки (количества заданий) и сведения к минимуу количества коммуникаций между компьютерами. Очевидно, что эту задачу можно сформулировать как задачу о минимальной бисекции в подходящим образом сформированном графе.
Стоит отметить, что во многих подобных ситуациях применение истинной аппроксимации необязательно, аппроксимации по двум критериям может быть вполне достаточно. Тем не менее, алгоритмы, описанные в разделе «Основные результаты», использовались для разработки алгоритмов для решения других задач – таких как (1) аппроксимационный алгоритм для решения задачи о минимальной бисекции в k-однородных гиперграфах [3]; (2) аппроксимационный алгоритм для варианта задачи о минимальном множественном разрезе [17]; (3) алгоритм эффективного определения невыполнимости случайных булевых формул в 2k-конъюнктивной нормальной форме (2k-SAT) при достаточно большом количестве дизъюнктов [5].
С учетом практического подхода были предложены и изучены многочисленные эвристики (алгоритмы без гарантии для наихудшего случая) для разбиения графов; их комплексный обзор можно найти в [1]. Одной из самых известных является эвристика локального поиска Лина-Кернигана для минимальной бисекции [11].
Открытые вопросы
В настоящее время существует большой разрыв между коэффициентом аппроксимации [math]\displaystyle{ O(log^{1,5} \; n) }[/math] для задачи о минимальной бисекции, полученным в результате применения теоремы 1, и сложностью известных для него результатов аппроксимации. Как упоминалось выше, задача о минимальной бисекции является NP-полной [9].
Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения [math]\displaystyle{ \epsilon \gt 0 \; }[/math] задача аппроксимации минимальной бисекции с дополнительным членом [math]\displaystyle{ n^{2 - \epsilon} \; }[/math] будет NP-полной. Фейге [7] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] не существует алгоритма [math]\displaystyle{ (4/3 - \varepsilon \;) }[/math]-аппроксимации задачи о минимальной бисекции. Хот [12] доказал, что для нахождения минимальной бисекции неприменима аппроксимационная схема с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения.
Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – например, при помощи алгоритма из [2], применив его вне подхода «черного ящика».
Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества [math]\displaystyle{ V = A \cup B \cup S \; }[/math], где |S| насколько возможно мало, при соблюдении следующего ограничения: [math]\displaystyle{ max \{ |A|, |B| \} \le n/2 \; }[/math], и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить аппроксимационный алгоритм с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейге и Яхалом дали отрицательный ответ [8].
См. также
См. вводную часть статьи Ароры, Рао и Вазирани [2].
Литература
1. Alpert, C.J., Kahng, A. B.: Recent directions in netlist partitioning: a survey. Integr. VLSI J. 19(1-2), 1-81 (1995)
2. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: 36th Annual Symposium on the Theory of Computing, pp. 222-231, Chicago, June 2004
3. Berman, P., Karpinski, M.: Approximability of hypergraph minimum bisection. ECCC Report TR03-056, Electronic Colloquium on Computational Complexity, vol. 10(2003)
4. Bui,T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inform. Process. Lett. 42(3), 153-159 (1992)
5. Coja-Oghlan, A.,Goerdt, A., Lanka, A., Schadlich, F.: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theor. Comput. Sci. 329(1-3), 1-45(2004)
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)
8. Feige, U., Yahalom, O.: On the complexity of finding balanced oneway cuts. Inf. Process. Lett. 87(1), 1-5 (2003)
7. Feige, U.: Relations between average case complexity and approximation complexity. In: 34th Annual ACM Symposium on the Theory of Computing, pp. 534-543, Montreal, May 19-21, 2002
9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company (1979)
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)
12. Khot, S.: Ruling out PTAS for graph Min-Bisection, Densest Subgraph and BipartiteClique. In:45th Annual IEEE Symposium on Foundations of Computer Science, pp. 136-145, Georgia Inst. of Technol., Atlanta 17-19Oct.2004
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
14. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787-832, 29th FOCS, 1988 (1999)
15. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615-627 (1980)
16. Rosenberg, A.L., Heath, L.S.: Graph separators, with applications. Frontiers of Computer Science. Kluwer Academic/Plenum Publishers, New York (2001)
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