Strong connectivity augmentation is FPT

Kristine Vitting Klinkby*, Pranabendu Misra, Saket Saurabh

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Augmenting an undirected or a directed graph (digraph) by adding new edges or arcs, to increase its connectivity to a target value, is a fundamental problem in combinatorial optimization and graph theory. In this paper we study the basic problem of augmenting an input digraph to make it strongly connected, which is known as the Strong Connectivity Augmentation problem. Here, the input is a digraph D = (V, A), a set of links L ⊆ V × V, and a positive integer k. The objective is to decide if there exists a subset F ⊆ L, of size at most k, such that D0 = (V, A ∪ F) is strongly connected. We consider the general version of this problem where, additionally, there is a weight function w : L → R+ on the links, and the goal is to find a minimum weight subset F ⊆ L of cardinality at most k, such that D0 = (V, A∪F) is strongly connected. We design an algorithm for this problem that runs in time 2O(k log k)nO(1), thereby showing that it is fixed parameter tractable (FPT). Here, n = |V |. This also resolves an open problem stated by Guo and Uhlmann more than a decade ago [ Networks 56(2): 131-142 (2010)].

Original languageEnglish
Title of host publicationProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsDániel Marx
Number of pages16
PublisherAssociation for Computing Machinery
Publication date2021
ISBN (Electronic)9781611976465
Publication statusPublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: 10. Jan 202113. Jan 2021


Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics
SeriesProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Bibliographical note

Publisher Copyright:
Copyright © 2021 by SIAM


Dive into the research topics of 'Strong connectivity augmentation is FPT'. Together they form a unique fingerprint.

Cite this