Дополнение графа до сильно связного

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

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

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

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

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

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

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

Неточность их алгоритма поиска пар вершин-источников и вершин-приёмников была позднее найдена и исправлена.

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

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

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

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

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