Связность графа
Ключевые слова и синонимы
Сильно связные подграфы; разреженные сертификаты
Постановка задачи
Неориентированный граф G называется k-связным (точнее, k-вершинно-связным), если удаление любых k-1 или меньшего числа вершин (с инцидентными им ребрами) не приводит к нарушению связности G. Аналогичным образом, граф называется k-реберно-связным, если удаление любых k-1 ребер не приводит к нарушению связности G. Согласно теореме Менгера, k-вершинно-связный граф содержит по меньшей мере k открытых вершинно-непересекающихся путей, соединяющих любую пару вершин. В k-вершинно-связных графах любую пару вершин соединяют k вершинно-непересекающихся путей. Связность графа равна наибольшему значению k, при котором он является k-связным. Задача вычисления связности графа и задача поиска k непересекающихся путей между заданной парой вершин могут быть решены при помощи алгоритмов нахождения максимального потока. Ребро называется критическим в k-связном графе, если после его удаления граф уже не будет k-связным.
Задача нахождения k-вершинно-связного (k-реберно-связного) подграфа минимальной мощности, содержащего все вершины данного графа, носит название k-VCSS (соответственно, k-ECSS) и для [math]\displaystyle{ k \ge 2 \; }[/math] имеет недетерминированную полиномиальную временную сложность. Рассмотрим некоторые результаты поиска приближенных минимальных решений задач k-VCSS и k-ECSS. Основное внимание будет уделяться простым графам. Простой аппроксимационный алгоритм рассматривает ребра согласно некоторому порядку и удаляет ребра, не являющиеся критическими. В результате работы создается k-связный подграф, в котором все ребра являются критическими; можно показать, что этот алгоритм является алгоритмом 2-аппроксимации (он выдает решение с не более чем kn ребрами в графе с n вершинами, и поскольку каждая вершина имеет степень не менее k, можно утверждать, что в графе должно быть kn/2 ребер).
Аппроксимационные алгоритмы, более эффективные относительно этого простого алгоритма, принадлежат к одной из двух категорий: алгоритмы на базе обхода в глубину (DFS) и на базе паросочетания.
Основные результаты
Нижние границы для k-связных остовных подграфов
Каждая вершина k-связного графа имеет по меньшей мере k инцидентных ей дуг. Следовательно, сумма степеней всех его вершин составляет по меньшей мере kn, где n – количество вершин графа. Поскольку в эту сумму каждое ребро входит дважды, мощность множества ребер составляет не менее kn/2. Назовем ее нижней границей степени. Несколько расширив эту идею, мы получим более сильную нижнюю границу мощности k-связного остовного подграфа исходного графа. Пусть [math]\displaystyle{ D_k \; }[/math] – подграф, у которого каждая вершина имеет степень не меньше k. В отличие от k-связного подграфа, [math]\displaystyle{ D_k \; }[/math] не имеет ограничений по связности. Согласно вышеприведенному рассуждению, [math]\displaystyle{ D_k \; }[/math] имеет не менее kn/2 ребер. Сведя задачу к задаче паросочетания, мы сможем вычислить [math]\displaystyle{ D_k \; }[/math] минимальной мощности за полиномиальное время; этот вариант будет называться нижней границей по паросочетанию.
Подходы на базе DFS
Данный алгоритм находит 3/2-аппроксимацию для 2-реберно-связного подграфа (2-ECSS). Примем некоторую вершину r за корень дерева и запустим алгоритм DFS. Все ребра графа теперь являются либо древесными, либо обратными. Обработаем дерево DFS в обратном порядке. Для каждого поддерева выполним следующее: если удаление ребра, ведущего от его корня к родителю, разбивает граф на два компонента, добавить самое далекое обратное ребро, ведущее из этого поддерева, у которого вторая конечная точка является наиболее близкой к r. Можно показать, что количество обратных ребер, добавленных алгоритмом, не превышает половины размера Opt.
Обобщив этот алгоритм, можно решить задачу 2-VCSS с тем же коэффициентом аппроксимации, если добавлять тщательно отобранные обратные ребра, позволяющие удалять древесные ребра. В случае, когда удалить древесное ребро невозможно, алгоритм добавляет вершину к множеству независимых вершин I. В конечном итоге количество использованных ребер будет меньше n + |I|. Поскольку Opt не меньше max(n, 2|I|), мы получаем аппроксимацию с коэффициентом 3/2.
Алгоритм можно расширить на задачу вычисления k-ECSS, применяя этот подход k/2 раз и на каждом этапе увеличивая связность на 2. Было показано, что описанный алгоритм достигает эффективности 1.61.
Подходы на базе паросочетания
Некоторые аппроксимационные алгоритмы для вычисления k-ECSS и k-VCSS используют подграф минимальной мощности [math]\displaystyle{ D_k \; }[/math] в качестве отправной точки, дополняя его добавочными ребрами таким образом, чтобы удовлетворять ограничениям связности. При использовании этого подхода получаются лучшие коэффициенты, чем при использовании подхода на базе DFS.
Алгоритм вычисления k-VCSS с коэффициентом [math]\displaystyle{ 1 + \frac{1}{k} }[/math]. Найти подграф [math]\displaystyle{ D_{k-1} \; }[/math] минимальной мощности. Добавить столько дополнительных ребер, чтобы он стал k-связным. На этом этапе мы гарантируем, что добавленные ребра являются критическими. Из теоремы Мадера известно, что в k-связном графе цикл из критических ребер содержит по меньшей мере одну вершину степени k. Поскольку все ребра, добавляемые алгоритмом на втором этапе, являются критическими, не может существовать цикла, порожденного этими ребрами, так как степень всех вершин в таком цикле должна быть не меньше k+1. Следовательно, на этом этапе добавляются не более n-1 ребер. Количество ребер, добавленных на первом этапе к минимальному подграфу [math]\displaystyle{ D_{k-1} \; }[/math], не превышает Opt — n/2. Общее количество ребер в полученном таким образом подграфе не превышает (1 + 1/k), умноженное на количество ребер в оптимальном k-VCSS.
Алгоритм вычисления k-ECSS с коэффициентом [math]\displaystyle{ 1 + \frac{2}{k+1} }[/math]. Теорема Мадера о циклах, порожденных критическими ребрами, действует только для вершинной связности, но не для реберной. В силу этого был предложен отдельный алгоритм для вычисления k-ECSS в графах, являющихся k-реберно-связными, но не являющихся k-связными. Этот алгоритм находит подграф [math]\displaystyle{ D_k \; }[/math] минимальной мощности и дополняет его минимальным количеством добавочных ребер, делая подграф k-реберно-связным. Количество ребер, добавленных на последнем этапе, не превышает [math]\displaystyle{ \frac{k}{k+1} (n-1) }[/math]. Поскольку количество добавленных на первом этапе ребер не превышает Opt, общее число ребер в итоге не превышает [math]\displaystyle{ (1 + \frac{2}{k+1}) Opt }[/math].
Улучшенные алгоритмы для малых значений k. Для [math]\displaystyle{ k \in \{ 2, 3 \} }[/math] алгоритмы были улучшены за счет более аккуратного применения вышеизложенных действий, удаления не являющихся необходимыми ребер и получения улучшенных нижних границ. Для k = 2 может быть получена аппроксимация с коэффициентом 4/3 при помощи формирования покрытия путями и циклами с минимальной мощностью [math]\displaystyle{ D_2 \; }[/math] и 2-связывания их с «основным» компонентом, по одному на каждом шагу. Небольшие циклы и пути позволяют удалять ребро, когда они 2-связаны с ядром, что обеспечивает возможность применения простого амортизационного анализа. Можно обобщить этот метод на задачу 3-ECSS и получить аппроксимацию с коэффициентом 4/3.
Были предложены гибридные подходы, использующие покрытие путями и циклами для создания специфического DFS-дерева исходного графа и затем организации 2-связывания дерева в стремлении к удалению ребер везде, где это возможно. Использование таких подходов позволяет получить следующие коэффициенты аппроксимации в лучшем случае: 5/4 для задачи 2-ECSS, 9/7 для 2-VCSS и 5/4 для 2-VCSS в 3-связных графах.
Применение
Одной из основных областей применения является проектирование сетей, в том числе конструирование сильно связных сетей низкой стоимости.
Литература
Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [3]. Быстрые алгоритмы 2-аппроксимации для задач k-ECSS и k-VCSS изучали Нагамочи и Ибараки [13]. Алгоритмы на базе DFS для задачи 2-связности были предложены Хуллером и Вишкином [11]. Они получили следующие коэффициенты аппроксимации: 3/2 для задачи 2-ECSS, 5/3 для 2-VCSS и 2 для взвешенной k-ECSS. Значение коэффициента для 2-VCSS было улучшено в следующих работах: до 3/2 – Гарг и коллеги [6], до 4/3 – Вемпала и Ветта [14], до 9/7 – Губбала и Рагавачари [7]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [2] изучали задачу k-VCSS для взвешенных ребер и разработали аппроксимационный алгоритм со сложностью O(log k) для графов, содержащих не менее [math]\displaystyle{ 6k^2 \; }[/math] вершин.
Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [1]. Они предложили алгоритмы с коэффициентами [math]\displaystyle{ 1 + \frac{1}{k} }[/math] для k-VCSS, [math]\displaystyle{ 1 + \frac{2}{k+1} }[/math] для k-ECSS, [math]\displaystyle{ 1 + \frac{1}{k} }[/math] для k-VCSS в ориентированных графах и [math]\displaystyle{ 1 + \frac{4}{ \sqrt{k} } }[/math] для k-ECSS в ориентированных графах. Вемпала и Ветта [14] сумели получить коэффициент 4/3 для задачи 2-VCSS. Далее результат улучшили Криста и Кумар [12], предложившие гибридный подход, при помощи которого Джоти и коллеги разработали алгоритм с коэффициентом 5/4 [9]. Алгоритм 3/2-аппроксимации для задачи 3-ECSS, предложенный Габовым [5], работает на мультиграфах, тогда как более ранний алгоритм Черияна и Туримеллы позволяет получить такое же значение коэффициента только на простых графах. Губбала и Рагавачари улучшили это значение до 4/3 [8].
1. Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528-560 (2000)
2. Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput.32(4), 1050-1055 (2003)
3. Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial optimization. Wiley, New York (1998)
4. Gabow, H.N.: Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. In: SODA, 2003, pp. 460-469
5. Gabow, H.N.: An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. SIAM J. Discret. Math. 18(1), 41-70 (2004)
6. Garg, N., Vempala, S., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: SODA, 1993, pp. 103-111
7. Gubbala, P., Raghavachari, B.: Approximation algorithms for the minimum cardinality two-connected spanning subgraph problem. In: JCinger, M., Kaibel, V. (eds.) IPCO. Lecture Notes in Computer Science, vol. 3509, pp. 422-436. Springer, Berlin (2005)
8. Gubbala, P., Raghavachari, B.: A 4/3-approximation algorithm for minimum 3-edge-connectivity. In: Proceedings of the Workshop on Algoriths and Data Structures (WADS) August 2007, pp. 39-51. Halifax (2007)
9. Jothi, R., Raghavachari, B.,Varadarajan, S.: A 5/4-approximation algorithm for minimum 2-edge-connectivity. In: SODA, 2003, pp. 725-734
10. Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. J. Algorithms 21 (2), 434-450(1996)
11. Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J.ACM 41(2), 214-235 (1994)
12. Krysta, P., Kumar, V.S.A.: Approximation algorithms for minimum size 2-connectivity problems. In: Ferreira, A., Reichel, H. (eds.) STACS. Lecture Notes in Computer Science, vol. 2010, pp. 431 ^42. Springer, Berlin (2001)
13. Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7(5-6), 583-596 (1992)
14. Vempala, S., Vetta, A.: Factor 4/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX. Lecture Notes in Computer Science, vol. 1913, pp. 262-273. Springer, Berlin (2000)
