Source-linked AI summary
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Tomohiro Koana, Soh Kumabe
TL;DR
SCA asks whether a DAG can be made strongly connected by adding a bounded number of prescribed links within a weight budget. The paper reduces SCA to SCSS with two edge costs and answers affirmatively the questions about single-exponential algorithms and polynomial kernels.
Problem
SCA asks whether a directed acyclic graph can be made strongly connected by adding prescribed links within a bound on their number and total weight.
Source: §1 · p. 1Method
The paper reduces SCA to Strongly Connected Spanning Subgraph with two edge costs.
Source: §1.1 · p. 2, §4 · p. 8Results
Weighted SCA is solvable in O*(9^k) time and has a kernel with O(k^4) vertices and O(k^16) bits; unweighted SCA is solvable in O*(4^k) time and has a kernel with O(k^3) vertices.
Source: §1.1 · p. 3Takeaways & Limitations
The results answer affirmatively whether SCA admits single-exponential parameterized algorithms and polynomial kernels.
Source: §1.1 · p. 2
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies adding a bounded number of prescribed links, within a weight budget, to make a DAG strongly connected. It answers open questions on single-exponential algorithms and polynomial kernels using a reduction to SCSS with two costs.
1 Introduction
- SCA asks whether at most k prescribed links, of total weight at most t, can make a DAG strongly connected; even edge-free inputs capture Directed Hamiltonian Cycle.Klinkby, Misra, and Saurabh gave an O*(2^{O(k log k)})-time algorithm and asked whether single-exponential algorithms and polynomial kernels exist.Source: §1 · pp. 1–2
1.1 Our contributions
- O*(9^k) time solves weighted SCA, while unweighted SCA takes O*(4^k); the paper also gives kernels with O(k^4) vertices and O(k^16) bits, and with O(k^3) vertices for the unweighted case.The results follow from a reduction to SCSS with two edge costs.Source: §1.1 · pp. 2–3
1.2 Related work
- Earlier work includes a single-exponential algorithm for unweighted SCSS, while single-exponential results for augmentation also cover plane SCA and some undirected settings.For unweighted SCA with every missing edge available, a minimum augmentation can be found in linear time using with the corrected construction of.Source: §1.2 · p. 3
2 Reduction to SCSS with two costs
Section 2 proves an equivalence between the augmentation instance and an SCSS instance with two costs, using terminals formed by the sources and sinks of the DAG. Its correctness argument preserves link and weight bounds when translating solutions between the instances.
2 Reduction to SCSS with two costs
- Polynomial-time layered shortest-path computations find the minimum weight of each terminal-to-terminal path using at most h links.The construction uses h+1 DAG layers, with zero-weight base edges within each layer and link edges between consecutive layers.Source: §2 · p. 4
- Expanding an SCSS solution into chosen terminal paths yields a feasible augmentation without exceeding its link or weight bounds.The union of path link sets uses at most the SCSS link cost and weight because link counts and weights are nonnegative.Source: §2 · p. 4
- For the reverse direction, Mader’s directed splitting theorem reduces a strongly connected graph to the terminals while preserving paths that use each augmentation link at most once.The proof balances nonterminals, repeatedly splits entering and leaving edge pairs, then reverses the splittings to obtain terminal paths.Source: §2 · p. 5
- Selecting SCSS edges for those terminal paths keeps the total link count and weight within the feasible augmentation’s bounds.Each selected edge’s link cost is the path’s number of links, and its second cost is no greater than the path weight.Source: §2 · p. 5
- The reduction maps the augmentation instance to an equivalent SCSS instance whose vertices are the at most 2k sources and sinks of the DAG.The proof establishes both directions of the yes-instance equivalence.Source: §2 · pp. 4–5
3 Single-exponential algorithms and a polynomial kernel
The paper uses dynamic programming on an SCSS instance to obtain single-exponential algorithms, and constructs smaller equivalent SCA instances for polynomial kernels. The resulting bounds are O^*(4^k) time and O(k^3) vertices for unweighted SCA, and O^*(9^k) time, O(k^4) vertices, and O(k^16) bits for general SCA.
3.1 Single-exponential algorithms
- The dynamic program builds a minimum-cost strongly connected spanning subgraph by starting with a directed cycle and adding ears.It stores path costs and ear-decomposition costs; transitions append an ear using a (min, +) subset convolution.Source: §3.1 · p. 6
- O^*(4^k) time for unweighted SCA and O^*(9^k) time for SCA with general link weights follow from dynamic programming on at most 2k terminals.The unweighted algorithm uses a single-cost SCSS instance; the weighted algorithm retains two edge costs.Source: §3.1 · p. 6
3.2 Polynomial kernels
- O(k^3) vertices suffice for the unweighted SCA kernel, which retains paths between terminals and compresses base-edge reachability.The construction preserves the existence of terminal paths using at most h links for every h from 0 to k.Source: §3.2 · pp. 6–7
- O(k^4) vertices and O(k^16) bits suffice for the general SCA kernel.The weighted construction retains paths for terminal pairs and link budgets, then applies Frank–Tardos weight reduction to bound the encoding size.Source: §3.2 · pp. 7–8
4 Conclusion
The reduction to SCSS with two edge costs yields single-exponential algorithms and polynomial kernels for SCA. The authors suggest it may also be useful for approximation algorithms, noting the success of Steiner Tree reductions in related undirected augmentation problems.
4 Conclusion
- The SCSS reduction may be useful for approximation algorithms for SCA, following successful Steiner Tree reductions in undirected augmentation.Related reductions yielded a 1.91-approximation for the unweighted problem and a (1.5 + ε)-approximation for the weighted problem for every fixed ε > 0.Source: §4 · p. 8
Declaration of generative AI use
The authors report that ChatGPT 6 Astra proposed a proof of the unweighted kernel result, which they used to extract the SCSS reduction. They also report using it to draft the manuscript, which they verified and revised and for which they take full responsibility.
Declaration of generative AI use
- ChatGPT 6 Astra proposed a proof of the unweighted kernel result, and the authors extracted the SCSS reduction from that proof.The authors also used ChatGPT 6 Astra to draft the manuscript, then verified and revised it and took full responsibility.Source: Declaration of generative AI use · p. 8