English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems thatare FPT when parameterized by the treewidth of the complement graph (calledco-treewidth). Since the degeneracy of a graph is at most its treewidth, theyalso introduced the study of co-degeneracy (the degeneracy of the complementgraph) as a parameter. In 1976, Bondy and Chv\'{a}tal [DM 1976] introduced thenotion of closure of a graph: let $\ell$ be an integer; the $(n+\ell)$-closure,$\operatorname{cl}_{n+\ell}(G)$, of a graph $G$ with $n$ vertices is obtainedfrom $G$ by recursively adding an edge between pairs of nonadjacent verticeswhose degree sum is at least $n+\ell$ until no such pair remains. A graphproperty $\Upsilon$ defined on all graphs of order $n$ is said to be$(n+\ell)$-stable if for any graph $G$ of order $n$ that does not satisfy$\Upsilon$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies$\Upsilon$ implies $d(u)+d(v)< n+\ell$. Duarte et al. [MFCS 2021] developed analgorithmic framework for co-degeneracy parameterization based on the notion ofclosures for solving problems that are $(n+\ell)$-stable for some $\ell$bounded by a function of the co-degeneracy. In this paper, we first determinethe stability of the property of having a bounded cycle cover. After that,combining the framework of Duarte et al. [MFCS 2021] with some results ofJansen, Kozma, and Nederlof [WG 2019], we obtain a $2^{\mathcal{O}(k)}\cdotn^{\mathcal{O}(1)}$-time algorithm for Minimum Cycle Cover on graphs withco-degeneracy at most $k$, which generalizes Duarte et al. [MFCS 2021] andJansen et al. [WG 2019] results concerning the Hamiltonian Cycle problem.

On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy