Strong connectivity augmentation solved with faster algorithms and smaller data
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Data Structures and Algorithms
Summary
Strong Connectivity Augmentation is a problem about making directed graphs fully connected by adding a limited number of links within a budget. The authors improved on previous work by designing faster algorithms that run in single-exponential time relative to the number of added links. They also show how to reduce the problem size significantly without losing important information, creating polynomial kernels. Their approach simplifies the problem to a related one involving two types of edge costs.
What this means in practice
- •For network engineers: Optimize adding links to directed networks for strong connectivity within budget constraints, improving reliability planning.
- •For transportation planners: Efficiently plan minimal additional routes in one-way traffic or logistics networks to ensure strong connectivity without overspending.
Authors
Tomohiro Koana, Soh Kumabe
Abstract
Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.