Сепараторы в графах

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

Сбалансированные сечения

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

Задача о (сбалансированном) сепараторе заключается в нахождении сечения минимального (реберного) веса в графе, такого, что два сегмента графа имеют примерно одинаковый (вершинный) вес.

Более формально: пусть даны неориентированный граф [math]\displaystyle{ G = (V, E) \; }[/math] с неотрицательной весовой функцией на ребрах [math]\displaystyle{ c: E \to \mathbb{R}_+ \; }[/math] и неотрицательной весовой функцией на вершинах [math]\displaystyle{ \pi : V \to \mathbb{R}_+ \; }[/math], а также константа [math]\displaystyle{ b \le 1/2 \; }[/math]. Сечение [math]\displaystyle{ (S : V \; \backslash \; S) }[/math] называется b-сбалансированным, или (b, 1 - b)-сепаратором, если [math]\displaystyle{ b \; \pi (V) \le \pi (S) \le (1 - b) \pi(V) \; }[/math] (где [math]\displaystyle{ \pi(S) \; }[/math] обозначает [math]\displaystyle{ \sum_{v \in S} \pi (v) \; }[/math]).

Задача 1 (b-сбалансированный сепаратор)

Дано: граф с взвешенными вершинами и ребрами [math]\displaystyle{ G = (V, E, c, \pi) \; }[/math], константа [math]\displaystyle{ b \le 1/2 \; }[/math].

Требуется: найти b-сбалансированный сепаратор ([math]\displaystyle{ (S : V \; \backslash \; S) }[/math].

Цель: минимизировать вес ребер [math]\displaystyle{ c( \delta(S)) \; }[/math].

Тесно связана с этой задачей следующая:

Задача 2 (самое разреженное сечение (для материальных потоков))

Дано: граф с взвешенными вершинами и ребрами [math]\displaystyle{ G = (V, E, c, \pi) \; }[/math].

Требуется: найти сечение [math]\displaystyle{ (S : V \; \backslash \; S) }[/math], минимизирующее соотношение [math]\displaystyle{ (c( \delta (S))) / (\pi (S) \pi (V \; \backslash \; S)) }[/math].

Задача 2 представляет собой наиболее общий случай задачи нахождения самого разреженного сечения, решенной Лейтоном и Рао. Если установить веса всех вершин равными 1, получим однородную версию этой задачи:

Задача 3 (самое разреженное сечение (однородное))

Дано: граф с взвешенными ребрами G = (V, E, c).

Требуется: найти сечение [math]\displaystyle{ (S : V \; \backslash \; S) }[/math], минимизирующее соотношение [math]\displaystyle{ (c( \delta (S))) / (|S| | V \; \backslash \; S |) }[/math].

Самое разреженное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче параллельного управления несколькими товарными потоками (задача 4). Экземпляр задачи управления несколькими товарными потоками определяется на графе с взвешенными ребрами: для каждого из k товаров обозначаются источник [math]\displaystyle{ s_i \in V \; }[/math], сток [math]\displaystyle{ t_i \in V \; }[/math] и спрос [math]\displaystyle{ D_i \; }[/math]. Допустимое решение этой задачи определяет для каждого товара функцию потока на E, таким образом направляя поток определенного объема из [math]\displaystyle{ s_i \; }[/math] в [math]\displaystyle{ t_i \; }[/math].

Веса ребер представляют их емкость (пропускную способность), каждому ребру e сопоставлено ограничение пропускной способности: максимальная сумма всех товарных потоков через ребро e не превышает его емкости c(e).

Задача 4 (параллельное управление несколькими товарными потоками)

Дано: граф с взвешенными ребрами [math]\displaystyle{ G = (V, E, c) \; }[/math], товары [math]\displaystyle{ (s_1, t_1, D_1), ..., (s_k, t_k, D_k) \; }[/math].

Требуется: обеспечить управление несколькими товарными потоками, направляющее [math]\displaystyle{ f D_i \; }[/math] единиц товара i из [math]\displaystyle{ s_i \; }[/math] в [math]\displaystyle{ t_i \; }[/math] для каждого i одновременно, не нарушая заданной емкости каждого ребра.

Цель: максимизация f.

Задача 4 может быть решена за полиномиальное время при помощи методов линейного программирования. Она также допускает произвольную аппроксимацию при помощи нескольких более эффективных комбинаторных алгоритмов (см. раздел «Реализация»). Максимальное значение f, для которого возможно управление несколькими товарными потоками, называется максимальным потоком для данного экземпляра задачи. Минимальным сечением является минимальное соотношение [math]\displaystyle{ (c( \delta (S)))/(D(S, V \; \backslash \; S)) \; }[/math], где [math]\displaystyle{ D(S, V \; \backslash \; S) = \sum_{i: | \{ s_i, t_i \} \; \cap \; S | = 1} D_i }[/math]. Эта двойственная интерпретация приводит нас к самой общей версии задачи – нахождению неоднородного самого разреженного сечения (задача 5).

Задача 5 (самое разреженное сечение (неоднородное))

Дано: граф с взвешенными ребрами [math]\displaystyle{ G = (V, E, c) \; }[/math], товары [math]\displaystyle{ (s_1, t_1, D_1), ..., (s_k, t_k, D_k) \; }[/math].

Требуется: найти минимальное сечение [math]\displaystyle{ (S : V \; \backslash \; S) }[/math], иначе говоря, сечение с минимальным соотношением [math]\displaystyle{ (c( \delta (S)))/(D(S, V \; \backslash \; S)) \; }[/math].

(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о самом разреженном сечении»).

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

Даже если все веса (ребер и вершин) равны 1, нахождение b-сбалансированного сечения с минимальным весом представляет собой NP-полную задачу (для b = 1/2 она превращается в задачу бисекции графа). Лейтон и Рао [23, 24] предложили псевдоаппроксимационный алгоритм для решения задачи общего вида.

Теорема 1. Существует алгоритм с полиномиальным временем выполнения, который для заданного взвешенного графа [math]\displaystyle{ G = (v, E, c, \pi), b \le 1/2 \; }[/math] и [math]\displaystyle{ b' \lt min \{ b, 1/3 \} \; }[/math] находит b'-сбалансированное сечение с весом в O((log n)/(b - b')) больше веса минимального b-сбалансированного сечения.

Алгоритм решает задачу нахождения самого разреженного сечения на заданном графе, отбрасывает сегмент с меньшим весом и рекурсивно повторяет операцию на сегменте с большим весом до тех пор, пока вес обоих сегментов самого разреженного сечения не достигнет значения [math]\displaystyle{ (1 - b') \; \pi (G) }[/math] или меньше. Теперь сегмент с большим весом, полученный в результате сечения на последней итерации, возвращается алгоритмом как один из сегментов сбалансированного сечения, а все остальные фрагменты графа – как второй сегмент. Поскольку сама по себе задача нахождения самого разреженного сечения является NP-полной, Лейтону и Рао вначале потребовался аппроксимационный алгоритм для ее решения.

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

Формулировка алгоритма непосредственно следует из теоремы 3.

Теорема 3. Существует алгоритм с полиномиальным временем выполнения, который находит сечение [math]\displaystyle{ (S : V \; \backslash \; S) }[/math] с соотношением [math]\displaystyle{ (c( \delta (S))) / (\pi (S) \pi (V \; \backslash \; S)) \in O(f \; log \; p) }[/math], где f – максимальный поток среди всех материальных товарных потоков, а p – количество вершин с ненулевым весом.

Доказательство теоремы 3 основано на решении формулировки задачи управления несколькими товарными потоками для линейного программирования и использовании этого решения для построения разреженного сечения.

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

Шахрохи и Матула [27] предложили теорему о максимальном потоке и минимальном сечении для специального случая задачи управления несколькими товарными потоками и использовали схожий подход на основе линейного программирования для доказательства полученного результата. Верхняя граница O(log n) для произвольного уровня спроса была доказана в работах Аумана и Рабани [6] и Линиала и др. [26]. В обоих случаях решение двойственной линейной программы для управления несколькими товарными потоками интерпретируется как конечная метрика и вкладывается в [math]\displaystyle{ \ell_1 \; }[/math] с искажением O (log n) при помощи вложения Бургейна [10]. Полученная в результате метрика [math]\displaystyle{ \ell_1 \; }[/math] представляет собой выпуклую комбинацию метрик сечений, из которой может быть извлечено сечение, с коэффициентом разреженности, который должен быть не ниже, чем коэффициент в комбинации.

Арора и др. [5] предложили псевдоаппроксимационный алгоритм с коэффициентом [math]\displaystyle{ O(\sqrt {log \; n}) }[/math] для нахождения сбалансированных сепараторов в случае однородных либо взвешенных материальных потоков, основанный на полуопределенной релаксации. Для неоднородной версии лучшую границу [math]\displaystyle{ O(\sqrt {log \; n} \; log \; log \; n) }[/math] демонстрирует алгоритм Ароры и др. [4]. Хот и Вишной [18] показали, что для неоднородной версии задачи полуопределенная релаксация [5] имеет разрыв целостности не менее [math]\displaystyle{ (log \; log \; n)^{1/6 - \delta} }[/math] для любого [math]\displaystyle{ \delta \gt 0 \; }[/math] и, более того, согласно их гипотезе об уникальной игре, (псевдо)аппроксимация задачи о сбалансированном сепараторе с любым константным коэффициентом является NP-полной. Краутгамер и Рабани [20] усилили разрыв целостности в задаче полуопределенного программирования (SDP) до [math]\displaystyle{ \Omega (log \; log \; n) }[/math]. Деванур и др. [11] продемонстрировали разрыв целостности в размере [math]\displaystyle{ \Omega (log \; log \; n) }[/math] для формулировки задачи SDP даже в однородном случае.

Реализация

Узким местом алгоритма поиска сбалансированного сепаратора является решение линейной программы для задачи управления несколькими товарными потоками. Для таких линейных программ было предложено немало быстрых приближенных решений [19, 22, 25]. В большинстве следующих работ алгоритм формирует [math]\displaystyle{ (1 + \epsilon) }[/math]-аппроксимацию, скрытая константа которой зависит от [math]\displaystyle{ \epsilon^{-2} \; }[/math]. Гарг и Кёнеманн [15], Флейшер [14] и Каракостас [16] предложили эффективные аппроксимационные схемы для задачи управления несколькими товарными потоками и сопутствующих задач с временем выполнения [math]\displaystyle{ \tilde{O}((k + m) \;m) }[/math] [15] и [math]\displaystyle{ \tilde{O} (m^2) \; }[/math] [14,16]. Бенцур и Карджер [7] предложили O(log n)-аппроксимацию задачи поиска самого разреженного сечения на базе рандомизированного алгоритма нахождения минимального разреза с временем выполнения [math]\displaystyle{ \tilde{O}(n^2) \; }[/math]. Наиболее быстрая на данный момент O(log n)-аппроксимация задачи поиска самого разреженного сечения (сбалансированного сепаратора) основана на прямо-двойственном подходе к полуопределенному программированию, предложена Аророй и Кейлом [3] и выполняется за время [math]\displaystyle{ O(m + n^{3/2})(\tilde{O}(m + n^{3/2}) }[/math], соответственно). В той же статье приведен алгоритм [math]\displaystyle{ O(\sqrt{log \; n}) }[/math]-аппроксимации с временем выполнения [math]\displaystyle{ O(n^2)(\tilde{O}(n^2) \; }[/math], соответственно), улучшивший предыдущее время [math]\displaystyle{ \tilde{O}(n^2) \; }[/math] алгоритма Ароры и др. [2]. Если [math]\displaystyle{ O(log^2 \; n) }[/math]-аппроксимация оказывается достаточной, то самое разреженное сечение может быть найдено за время [math]\displaystyle{ \tilde{O}(n^{3/2}) \; }[/math], а сбалансированный сепаратор – за время [math]\displaystyle{ \tilde{O}(m + n^{3/2}) \; }[/math] [17].

Применение

Многие задачи можно решить, используя подпрограммы поиска сбалансированного сепаратора или самого разреженного сечения. Коэффициент аппроксимации полученного алгоритма обычно прямо зависит от коэффициента соответствующей подпрограммы. В большинстве случаев граф рекурсивно разбивается на фрагменты сбалансированного размера. Помимо коэффициента аппроксимации O(log n), принадлежащего алгоритму поиска сбалансированного сепаратора, еще один коэффициент O(log n) возникает в силу глубины рекурсии. Ивен и др. [12] улучшили многие результаты на базе алгоритма сбалансированного сепаратора благодаря использованию метрик рассеяния, снизив гарантированный коэффициент аппроксимации с [math]\displaystyle{ O(log^2 \; n) }[/math] до O(log n log log n).

Некоторые приложения перечислены ниже; примеры, для которых не приведено ссылки, см. в [24].

• Линейное расположение минимального разреза и минимальное множество обратных дуг. Обе эти задачи решает один алгоритм [math]\displaystyle{ O(log^2 \; n) }[/math]-аппроксимации.

• Построение минимального хордального графа и упорядочение удалений [1]. Упорядочение удалений используется при решении разреженных систем линейных уравнений с симметричной матрицей. Алгоритм с коэффициентом аппроксимации [math]\displaystyle{ O(log^2 \; n) }[/math] [1] для построения хордального графа был улучшен до O(log n log log n) Ивеном и др. [12].

• Сбалансированные вершинные сечения. Стоимость сбалансированного сечения может измеряться в терминах веса вершин, удаленных из графа. Алгоритм поиска сбалансированного сепаратора можно легко расширить на такой случай с взвешенными вершинами.

• Проектирование СБИС. Бхатт и Лейтон [8] изучали несколько задач оптимизации для проектирования СБИС. Рекурсивное разбиение при помощи алгоритма поиска сбалансированного сепаратора ведет к созданию полилогарифмических аппроксимационных алгоритмов для нахождения количества пересечений, минимальной площади размещения схемы и других показателей.

• Древесная ширина и путевая ширина. Бодлендер и др. [9] показали способ аппроксимации древесной ширины с коэффициентом O(log n) и путевой ширины – с коэффициентом [math]\displaystyle{ O(log^2 \; n) }[/math] при помощи сбалансированных вершинных сепараторов.

• Бисекция. Фейге и Краутгамер [7] предложили [math]\displaystyle{ O( \alpha \; log \; n) }[/math]-аппроксимацию задачи минимальной бисекции при помощи любого алгоритма [math]\displaystyle{ \alpha \; }[/math]-аппроксимации для нахождения минимального сечения.

Экспериментальные результаты

Ланг и Рао [21] сравнивали вариант поиска самого разреженного сечения из [24] с методами декомпозиции графов для проектирования СБИС.

См. также

• Частичные задачи упаковки и покрытия
• Минимальная бисекция
• Самое разреженное сечение

Литература

Более подробные сведения и ссылки на дополнительные результаты см. в обзоре [28].

1. Agrawal, A., Klein, P.N., Ravi, R.: Cutting down on fill using nested dissection: provably good elimination orderings. In: Brualdi, R.A., Friedland, S., Klee, V. (eds.) Graph theory and sparse matrix computation. IMA Volumes in mathematics and its applications, pp. 31-55. Springer, New York (1993)

2. Arora, S., Hazan, E., Kale, S.: O(logn) approximation to sparsest cut in O(n2) time. In: FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 238-247. IEEE Computer Society, Washington (2004)

3. Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: STOC '07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 227-236. ACM (2007)

4. Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 553-562. ACM Press, New York (2005)

5. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 222-231. ACM Press, New York (2004)

6. Aumann, Y., Rabani, Y.: An (log ) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1),291-301 (1998)

7. Benczur, A.A., Karger, D.R.: Approximating s-t minimum cuts in 6(n2) time. In: STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 47-55. ACM Press, New York (1996)

8. Bhatt, S.N., Leighton, F.T.: A framework for solving vlsi graph layout problems. J. Comput. Syst. Sci. 28(2), 300-343 (1984)

9. Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238-255 (1995)

10. Bourgain, J.: On Lipshitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52,46-52 (1985)

11. Devanur, N.R., Khot, S.A., Saket, R., Vishnoi, N.K.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 537-546. ACM Press, New York (2006)

12. Even, G., Naor, J.S., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4), 585-616(2000)

13. Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM J. Comput. 31(4), 1090-1118 (2002)

14. Fleischer, L.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discret. Math. 13(4), 505-520 (2000)

15. Garg, N., Konemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p. 300. IEEE Computer Society, Washington (1998)

16. Karakostas, G.: Faster approximation schemes for fractional multicommodity flow problems. In: SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 166-173. Society for Industrial and Applied Mathematics, Philadelphia (2002)

17. Khandekar, R., Rao, S., Vazirani, U.: Graph partitioning using single commodity flows. In: STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 385-390. ACM Press, New York (2006)

18. Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into h. In: FOCS '07: Proceedings of the 46th Annual IEEE Symposium on Foundations and Computer Science, pp. 53-62. IEEE Computer Society (2005)

19. Klein, P.N., Plotkin, S.A., Stein, C., Tardos, Ё.: Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput. 23(3), 466-487 (1994)

20. Krauthgamer, R., Rabani, Y.: Improved lower bounds for embeddings into h. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 1010-1017. ACM Press, New York (2006)

21. Lang, K., Rao, S.: Finding near-optimal cuts: an empirical evaluation. In: SODA '93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pp. 212-221. Society for Industrial and Applied Mathematics, Philadelphia (1993)

22. Leighton, F.T., Makedon, F., Plotkin, S.A., Stein, C., Stein, Ё., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. J. Comput. Syst. Sci. 50(2), 228-243 (1995)

24. Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 422-431, IEEE Computer Society (1988)

25. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J.ACM 46(6), 787-832 (1999)

26. Leong, T., Shor, P., Stein, C.: Implementation of a combinatorial multicommodity flow algorithm. In: Johnson, D.S., McGeoch, C.C. (eds.) Network flows and matching. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 12, pp. 387-406. AMS, Providence (1991)

27. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Comb. 15(2), 215-245(1995)

28. Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37(2), 318-334 (1990)

29. Shmoys, D.B.: Cut problems and their applications to divide-and-conquer. In: Hochbaum, D.S. (ed.) Approximation algorithms for NP-hard problems, pp. 192-235. PWS Publishing Company, Boston, MA (1997)