Самый неплотный разрез

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

Разрез с минимальным отношением (Minimum ratio cut)

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

Неформально в задаче о самом неплотном разрезе (Sparsest Cut) цель заключается в том, чтобы разбить заданный граф на две или несколько больших частей, удалив при этом как можно меньше ребер. Задачи разбиения графов, подобные этой, занимают центральное место в теории сетевых потоков, геометрических вложениях и цепях Маркова, а также являются важнейшим компонентом подходов «разделяй и властвуй» в таких приложениях, как маршрутизация пакетов, проектирование СБИС и кластеризация.

Формально, если задан граф G = (V, E), то разреженность или реберное расширение непустого множества [math]\displaystyle{ S \subset V, |S| \le \frac{1}{2} |V| }[/math], определяется следующим образом:

[math]\displaystyle{ \alpha(S) = \frac{|E(S), V \backslash S|}{|S|} }[/math].

Разреженность графа, [math]\displaystyle{ \alpha(G) }[/math], определяется по формуле:

[math]\displaystyle{ \alpha(G) = min_{S \subset V, |S| \le \frac{1}{2} |V|} \; \alpha(S) }[/math].

Цель задачи о самом неплотном разрезе состоит в том, чтобы найти подмножество [math]\displaystyle{ S \subset V }[/math] с минимальной разреженностью и определить разреженность графа.

Первый аппроксимационный алгоритм для задачи Sparsest Cut был разработан Лейтоном и Рао в 1988 году [13]. Применяя релаксацию линейного программирования для данной задачи, они получили аппроксимацию с коэффициентом O(log n), где n – размер входного графа. Впоследствии Арора, Рао и Вазирани [4] улучшили алгоритм Лейтона и Рао с помощью релаксации полуопределенного программирования, аппроксимировав задачу с точностью до коэффициента [math]\displaystyle{ O(\sqrt{log \; n}) }[/math].

Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу о сбалансированном сепараторе. Разбиение [math]\displaystyle{ (S, V \backslash S) }[/math] графа G называется c-сбалансированным сепаратором для [math]\displaystyle{ 0 \lt c \le \frac{1}{2} }[/math], если и [math]\displaystyle{ S }[/math] и [math]\displaystyle{ V \backslash S }[/math] имеют не менее c|V| вершин. Целью задачи о сбалансированном сепараторе является поиск c-сбалансированного разбиения с минимальной разреженностью, которая обозначается как [math]\displaystyle{ \alpha_c(G) }[/math].

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

Арора и др. предлагают [math]\displaystyle{ O(\sqrt{log \; n}) }[/math]-псевдоаппроксимацию задачи о сбалансированном сепараторе с помощью полуопределенного программирования. В частности, для константы [math]\displaystyle{ c \in (0, \frac{1}{2}] }[/math] они получили сепаратор с балансом c', который несколько хуже c (то есть c' < c), но с разреженностью в пределах [math]\displaystyle{ O(\sqrt{log \; n}) }[/math] от разреженности оптимального c-сбалансированного сепаратора.

Теорема 1. Пусть имеется граф G = (V, E) и пусть [math]\displaystyle{ \alpha_c(G) }[/math] – минимальное реберное расширение c-сбалансированного сепаратора в этом графе. Тогда для любой фиксированной константы a < 1 существует алгоритм с полиномиальным временем выполнения для нахождения c'-сбалансированного сепаратора в G, где c' [math]\displaystyle{ \ge }[/math] ac, имеющий реберное расширение не более [math]\displaystyle{ O(\sqrt{log \; n } \; \alpha_c(G)) }[/math].

Расширяя эту теорему на несбалансированные разбиения, Арора и др. получили следующий результат:

Теорема 2. Пусть G = (V, E) – граф с разреженностью [math]\displaystyle{ \alpha(G) }[/math]. Тогда существует алгоритм с полиномиальным временем выполнения для нахождения разбиения [math]\displaystyle{ (S, V \backslash S) }[/math], где [math]\displaystyle{ S \subset V, S \ne 0 }[/math], имеющего разреженность не более [math]\displaystyle{ O(\sqrt{log \; n} \; \alpha(G)) }[/math].

Важным вкладом Ароры и коллег является новая геометрическая характеристика векторов в n-мерном пространстве, снабженном метрикой квадратичного евклидова расстояния. Этот результат имеет самостоятельное значение и вдохновил иследователей на улучшение коэффициентов аппроксимации для ряда других задач разбиения (см., например, [1, 5, 6, 7, 11]).

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

Определение 1 (Опр. 4 в [4]). Пусть [math]\displaystyle{ \vec x_1, \vec x_2, ..., \vec x_n }[/math] – множество из n точек в пространстве [math]\displaystyle{ \mathcal{R}^n }[/math], снабженном квадратично-евклидовой метрикой [math]\displaystyle{ d(x, y) = \parallel x - y \parallel_2^2 }[/math]. Множество точек считается [math]\displaystyle{ (t, \gamma, \beta) }[/math]-растяженным в масштабе [math]\displaystyle{ \ell }[/math], если для хотя бы части [math]\displaystyle{ \gamma }[/math] всех n-мерных единичных векторов u существует частичное соответствие [math]\displaystyle{ M_u = \{ (x_i, y_i) \} _i }[/math] между этими точками, причем [math]\displaystyle{ |M_u| \ge \beta n }[/math], такое, что для всех [math]\displaystyle{ (x, y) \in M_u, d(x, y) \le \ell^2 }[/math] и [math]\displaystyle{ \langle u, \vec x - \vec y \rangle \ge t \ell / \sqrt{n} }[/math]. Здесь [math]\displaystyle{ \langle \cdot , \cdot \rangle }[/math] обозначает скалярное произведение двух векторов.

Теорема 3. Для любых [math]\displaystyle{ \gamma, \beta \gt 0 }[/math] существует константа [math]\displaystyle{ C = C(\gamma, \beta) }[/math], такая, что если [math]\displaystyle{ t \gt C \; log^{1/3} n }[/math], то никакое множество из n точек в пространстве [math]\displaystyle{ \mathcal{R}^n }[/math] не может быть [math]\displaystyle{ (t, \gamma, \beta) }[/math]-растяженным для любого масштаба [math]\displaystyle{ \ell }[/math].

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

Применение

Одним из основных способов применения сбалансированных сепараторов является повышение производительности алгоритмов «разделяй и властвуй» для различных задач оптимизации.

Одним из примеров является задача о минимальном разрезе с линейным расположением. В этой задаче цель заключается в упорядочении вершин заданного n-вершинного графа G от 1 до n таким образом, чтобы минимизировать пропускную способность наибольшего из разрезов ({1, 2, ..., i}, {i + 1, ..., n}), i [math]\displaystyle{ \in }[/math] [1, n]. При наличии [math]\displaystyle{ \rho }[/math]-аппроксимации задачи о сбалансированном сепараторе следующий алгоритм «разделяй и властвуй» дает [math]\displaystyle{ O(\rho \; log \; n) }[/math]-аппроксимацию задачи о минимальном разрезе с линейным упорядочением: следует найти сбалансированный сепаратор в графе, затем рекурсивно упорядочить две части и объединить эти упорядочения. Аппроксимация следует из того, что если в графе имеется сбалансированный сепаратор с расширением [math]\displaystyle{ \alpha_c(G) }[/math], то на каждом уровне разрезается только [math]\displaystyle{ O(\rho n \alpha_n(G)) }[/math] ребер, а учитывая, что сбалансированный сепаратор вычисляется на каждом шаге, количество уровней рекурсии составляет не более O(log n).

Аналогичные подходы могут быть использованы для решения таких задач, как проектирование СБИС и гауссово исключение. Более подробную информацию по этим темам см. в обзоре Шмойса [14].

Задача о самом неплотном разрезе также тесно связана с проблемой вложения квадратично-евклидовой метрики в Манхэттенскую метрику ([math]\displaystyle{ \ell_1 }[/math]) с малым искажением. В частности, разрыв целостности релаксации полуопределенного программирования Ароры и др. для задачи о разрезе (обобщенной на включение весов вершин и пропускной способности ребер) в точности равен наихудшему искажению для вложения квадратично-евклидовой метрики в манхэттенскую метрику. Используя технологию, представленную Аророй и коллегами, были получены улучшенные вложения квадратично-евклидовой метрики в манхэттенскую метрику [5, 7].

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

Показатели сложности аппроксимации для задачи о самом неплотном разрезе довольно слабы. Недавно Чужой и Ханна [9] показали, что эта задача является APX-сложной, то есть существует константа [math]\displaystyle{ \epsilon \gt 0 }[/math], такая, что [math]\displaystyle{ (1 + \epsilon) }[/math]-аппроксимационный алгоритм для нее будет означать равенство P=NP. Предполагается, что взвешенная версия задачи NP-сложна для аппроксимации с коэффициентом, лучшим, чем [math]\displaystyle{ O((log \; log \; n)^c) }[/math] для некоторой постоянной c, но справедливость этого утверждения показана только в предположении версии так называемой гипотезы об уникальной игре [8, 12]. С другой стороны, известно, что релаксация полуопределенного программирования Ароры и др. имеет разрыв целостности [math]\displaystyle{ \Omega (log \; log \; n) }[/math] даже в невзвешенном случае [10]. Доказательство безусловной суперконстантной сложности для взвешенного или невзвешенного варианта задачи о самом неплотном разрезе, а также получение [math]\displaystyle{ o(\sqrt{log \; n}) }[/math]-аппроксимаций для этих задач остаются нерешенными вопросами.

Ориентированная версия задачи Sparset Cut также изучалась, и для нее известна сложность аппроксимации с точностью до [math]\displaystyle{ 2^{\Omega(log^{1 - \epsilon} n)} }[/math] [9]. С другой стороны, лучшая аппроксимация, известная для этой задачи, дает только полиномиальный коэффициент – а именно, [math]\displaystyle{ O(n^{11/23} log^{O(1)} n) }[/math], полученный Аггарвалом, Алоном и Чарикаром [2].

Литература

1. Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: O(log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, May 2005, pp. 573-581

2. Aggarwal, A., Alon, N., Charikar, M.: Improved approximations for directed cut problems. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), San Diego, June 2007, pp. 671-680

3. Arora, S., Hazan, E., Kale, S.: An O(logn) approximation to SPARSEST CUT in O(n2) time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), Rome, ITALY, 17-19 October 2004, pp. 238-247

4. Arora, S., Rao, S., Vazirani, U.: Expander Flows, Geometric Embeddings, and Graph Partitionings. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, June 2004, pp. 222-231

5. Arora, S., Lee, J., Naor, A.: Euclidean Distortion and the Sparsest Cut. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, May 2005, pp. 553-562

6. Arora, S., Chlamtac, E., Charikar, M.: New approximation guarantees for chromatic number. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), Seattle, May 2006, pp. 215-224

7. Chawla, S., Gupta, A., Racke, H.: Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, January 2005, pp. 102-111

8. Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the Hardness of Approximating Sparsest Cut and Multi-cut. In: Proceedings of the 20th IEEE Conference on Computational Complexity (CCC), San Jose, June 2005, pp. 144-153

9. Chuzhoy, J., Khanna, S.: Polynomial flow-cut gaps and hardness of directed cut problems. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), San Diego, June 2007 pp. 179-188

10. Devanur, N., Khot, S., Saket, R., Vishnoi, N.: Integrality gaps for Sparsest Cut and Minimum Linear Arrangement Problems. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), Seattel, May 2006, pp. 537-546

11. Feige, U.,Hajiaghayi,M., Lee, J.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, May 2005, pp. 563-572

12. Khot, S., Vishnoi, N.:The Unique Games Conjecture, Integrality Gap for Cut Problems and the Embeddability of Negative-Type Metrics into^i .In: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, October 2005, pp. 53-62

13. Leighton, F.T., Rao, S.B.: An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms. In: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS), White Plains, October 1988, pp. 422^31

14. Shmoys, D.B.: Cut problems and their application to divide-and-conquer. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, pp. 192-235. PWS Publishing, Boston (1997)