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

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

Разрез с минимальным отношением (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].

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

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

Арора и др. предлагают O(plogn)-псевдоаппроксимацию задачи о сбалансированном сепараторе с помощью полуопределенного программирования. В частности, для константы c 2 (0, j] они получили сепаратор с балансом c0, что несколько хуже c (то есть c0 < c), но с разреженностью в пределах O(logn) от разреженности оптимального c-сбалансированного сепаратора.

Теорема 1. Пусть дан граф G = (V, E) и пусть ac(G) – минимальное реберное расширение c-сбалансированного сепаратора в этом графе. Тогда для любой фиксированной константы a < 1 существует алгоритм с полиномиальным временем выполнения для нахождения c0-сбалансированного сепаратора в G, при c0 > ac, имеющий реберное расширение не более

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

Теорема 2. Пусть G = (V, E) – граф с разреженостью a(G). Тогда существует алгоритм с полиномиальным временем выполнения для нахождения разбиения (S; Vn S), при S С V, S ф ;, имеющего разреженность не более 0(y/logna(G)).

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

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

Определение 1 (Опр. 4 в [4]). Пусть xE1; xE 2... , xEn – множество из n точек в Rn, снабженное квадратично-евклидовой метрикой d(x; y) = jjx - yjj22. Множество точек считается (t y, f$)-растяжимым в масштабе I, если для хотя бы части у всех n-мерных единичных векторов u существует частичное соответствие Mu = f(xi; yi)gi между этими точками, причем jMu j > fin, такое, что для всех (x; y) 2 Mu, d(x; y) < I2 и hu; x - y) > ttlsfn. Здесь (-, -) обозначает скалярное произведение двух векторов.

Теорема 3. Для любых y, f$ > 0 существует константа С = C(y, fi) такая, что если t > Clog1/3 n, то никакое множество из n точек в Rn не может быть (t y, f$)-растяжимым для любого масштаба I.

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

Применение

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

Одним из примеров является задача о минимальном разрезе с линейным расположением. В этой задаче цель заключается в упорядочении вершин заданного n-вершинного графа G от 1 до и таким образом, чтобы минимизировать емкость наибольшего из разрезов ({1,2,--- , i},{i + I,--- , и}), i e [1, и]. При наличии p-аппроксимации задачи о сбалансированном разделителе, следующий алгоритм «разделяй и властвуй» дает O(p log n)-аппроксимацию задачи о минимальном разрезе с линейным упорядочением: следует найти сбалансированный сепаратор в графе, затем рекурсивно упорядочить две части и объединить эти упорядочения. Аппроксимация следует из того, что если в графе имеется сбалансированный сепаратор с расширением ac(G), то на каждом уровне разрезается только O(pnan(G)) ребер, а учитывая, что сбалансированный сепаратор вычисляется на каждом шаге, количество уровней рекурсии составляет не более O(log n). Аналогичные подходы могут быть использованы для решения таких задач, как проектирование СБИС и гауссово исключение. Более подробную информацию по этим темам см. в обзоре Шмойса [14].

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

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

Показатели сложности аппроксимации для задачи о самом неплотном разрезе довольно слабы. Недавно Чужой и Ханна [9] показали, что эта задача является APX-сложной, то есть существует константа e > 0, такая, что (1 + e)-аппроксимационный алгоритм для нее будет означать равенство P=NP. Предполагается, что взвешенная версия

задачи NP-сложна для аппроксимации с коэффициентом, лучшим, чем O((loglog n)c) для некоторой постоянной c, но известно, что это верно только в предположении версии так называемой гипотезы об уникальной игре [8, 12]. С другой стороны, известно, что релаксация полуопределенного программирования Ароры и др. имеет разрыв целостности Q (log log n) даже в невзвешенном случае [ ]. Доказательство безусловной суперконстантной сложности для взвешенного или невзвешенного варианта задачи о самом неплотном разрезе, а также получение o(plogn)-аппроксимаций для этих задач остаются нерешенными вопросами.

Ориентированная версия задачи Sparset Cut также изучалась, и для нее известна сложность аппроксимации с точностью до 2^(los e "' [ ]. С другой стороны, лучшая аппроксимация, известная для этой задачи, дает только полиномиальный коэффициент – а именно O(n11/23 logO(1) n), полученный Аггарвалом, Алоном и Чарикаром [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)