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 study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $\chi_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $\chi_\mathrm{stable}(G)$. This shows that $\chi_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
Tomohiro Koana, Y. Oh, Hirotaka Yoneda· 0 citations
We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is $2$-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted $\lambda$-vertex-connectivity augmentation for every $\lambda\leq 4$ [Carmesin and Ramanujan, SODA 2026], and an $O^*((k+\lambda)^{O(k)})$-time algorithm for arbitrary $\lambda$ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time $O^*(36^kW)$. Thus, for $\lambda=2$, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. We reduce the problem to a boundary-pair variant of $2$-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying M\"obius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the $2$-vertex-connected spanning graphs.
The results reveal that, in this setting, MCIS is strictly harder than ISI, and it is shown that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.
Tomohiro Koana, Soh Kumabe, Y. Otachi· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
