The SCA problem can be solved in time and admits a polynomial kernel with vertices and bits and the algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.
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.
We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the...
D. Lokshtanov, Saket Saurabh, Jie Xue· 0 citations
Alternative parameterizations of the k-core problem are investigated to identify conditions under which it can be placed into sub-polynomial complexity classes, and the boundary of parallel tractability for the k-core problem is explored.
Aldous and Fill (2002) conjectured that the maximum relaxation time of a random walk on a connected regular graph with $n$ vertices is bounded above by $(1+o(1))\frac{3n^2}{2\pi^2}$, with asymptotic equality for even $n$. Since the relaxation time of a $d$-regular graph $G$ is $d/\mu(G)$, where $\mu(G)$ denotes its alg...
The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $...
Zi-Mo Sheng, Ming-Yu Xiao· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
