PROFILPELAJAR.COM

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

Задача о дополнении графа до сильно связного была сформулирована Эсвараном Капали и Робертом Тарьяном в 1976 году. Они доказали, что взвешенная версия задачи является NP-полной, а невзвешенная версия может быть решена за линейное время^[1]. Дальнейшее исследование задачи позволило найти приближённый алгоритм и параметризованную сложность для взвешенной версии^[2]^[3].

Невзвешенная версия

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

Пусть $s$ ― количество вершин-источников в конденсации (компонент сильной связности с как минимум одной исходящей дугой, но без входящих), $t$ ― количество вершин-стоков (компонент сильной связности с как минимум одной входящей дугой, но без исходящих) и $q$ ― количество изолированных вершин в конденсации. Тогда число дуг, которые необходимо добавить, как минимум $\max(s+q,t+q)$ . Это следует из того, что $s+q$ дуг необходимо добавить, чтобы у каждого источника или изолированной вершины появилась хотя бы одна входящая дуга. Аналогично, $t+q$ дуг необходимо добавить, чтобы у каждого стока или изолированной вершины появилась хотя бы одна исходящая дуга. Алгоритм для решения задачи находит в точности $\max(s+q,t+q)$ необходимых для добавления дуг^[1].

Алгоритм Эсварана и Тарьяна использует поиск в глубину по конденсации графа, чтобы найти все пары источников и стоков, обладающие следующими свойствами:^[1]

Из источника в каждой паре можно достичь стока в этой паре по пути, существующем в исходном графе.
Из каждого источника, у которого нет пары, можно достичь некоторого стока, у которого пара есть.
Каждый сток, у которого нет пары, достижим из некоторого источника, у которого пара есть.

Неточность их алгоритма поиска пар источников и стоков была позднее найдена и исправлена^[4].

Когда все вышеописанные пары найдены, дополнить граф до сильно связного можно, добавив в него следующие три набора дуг:^[1]

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

Общее число дуг в данных трёх наборах равно $\max(s+q,t+q)$ ^[1].

Взвешенная и параметризованная версия

Во взвешенной версии задачи каждая добавляемая дуга имеет заданный вес. Цель задачи ― выбрать множество добавляемых дуг с минимальным суммарным весом так, чтобы исходный граф стал сильно связным. Данная задача является NP-полной.^[1] 2-приближённый алгоритм был предложен Frederickson & Ja'Ja' (1981).^[2] Параметризованная и взвешенная версия задачи, в которой необходимо добавить не более чем $k$ дуг с минимальным суммарным весом, сделав граф сильно связным, является FPT-задачей^[3].

Ссылки

↑ ¹ ² ³ ⁴ ⁵ ⁶ Эсваран, Капали П.; Тарьян, Р. Андре (1976), "Augmentation problems", en:SIAM Journal on Computing, 5 (4): 653–665, doi:10.1137/0205044, MR 0449011
↑ ¹ ² Frederickson, Greg N.; Ja'Ja', Joseph (1981), "Approximation algorithms for several graph augmentation problems", en:SIAM Journal on Computing, 10 (2): 270–283, doi:10.1137/0210019, MR 0615218
↑ ¹ ² Klinkby, Kristine Vitting; Misra, Pranabendu; Saurabh, Saket (January 2021), "Strong connectivity augmentation is FPT", Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, pp. 219–234, doi:10.1137/1.9781611976465.15
↑ Raghavan, S. (2005), "A note on Eswaran and Tarjan's algorithm for the strong connectivity augmentation problem", in Golden, Bruce; Raghavan, S.; Wasil, Edward (eds.), The Next Wave in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces Series, vol. 29, Springer, pp. 19–26, doi:10.1007/0-387-23529-9_2