On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy
share
In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems that are FPT when parameterized by the treewidth of the complement graph (called co-treewidth). Since the degeneracy of a graph is at most its treewidth, they also introduced the study of co-degeneracy (the degeneracy of the complement graph) as a parameter. In 1976, Bondy and Chvátal [DM 1976] introduced the notion of closure of a graph: let ℓ be an integer; the (n+ℓ)-closure, cl_n+ℓ(G), of a graph G with n vertices is obtained from G by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least n+ℓ until no such pair remains. A graph property Υ defined on all graphs of order n is said to be (n+ℓ)-stable if for any graph G of order n that does not satisfy Υ, the fact that uv is not an edge of G and that G+uv satisfies Υ implies d(u)+d(v)< n+ℓ. Duarte et al. [MFCS 2021] developed an algorithmic framework for co-degeneracy parameterization based on the notion of closures for solving problems that are (n+ℓ)-stable for some ℓ bounded by a function of the co-degeneracy. In this paper, we first determine the stability of the property of having a bounded cycle cover. After that, combining the framework of Duarte et al. [MFCS 2021] with some results of Jansen, Kozma, and Nederlof [WG 2019], we obtain a 2^𝒪(k)· n^𝒪(1)-time algorithm for Minimum Cycle Cover on graphs with co-degeneracy at most k, which generalizes Duarte et al. [MFCS 2021] and Jansen et al. [WG 2019] results concerning the Hamiltonian Cycle problem.
READ FULL TEXT