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

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

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

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

править

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

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

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

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

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

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

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

Общее число дуг в данных трёх наборах равно  [1].

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

править

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

Ссылки

править
  1. 1 2 3 4 5 6 Эсваран, Капали П.; Тарьян, Р. Андре (1976), "Augmentation problems", en:SIAM Journal on Computing, 5 (4): 653—665, doi:10.1137/0205044, MR 0449011
  2. 1 2 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
  3. 1 2 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
  4. 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