论文标题
关于具有有限共同定位的图表上的最小周期覆盖问题
On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy
论文作者
论文摘要
在2021年，Duarte，Oliveira和Souza [MFCS 2021]显示了一些问题，这些问题是通过补体图（称为co-Treewidth）参数化时FPT的。由于图的堕落最多是其树宽的，因此他们还引入了共同定位的研究（补体图的退化）作为参数。 1976年，邦迪（Bondy）和奇瓦塔尔（Chvátal）[DM 1976]介绍了闭合图的概念：让$ \ ell $成为整数； $（n+\ ell）$ - 关闭，$ \ operatorAtorname {cl} _ {n+\ ell}（g）$，图$ g $，带有$ n $ dertices的$ g $是通过递归添加$ g $的$ n $ dertices来获得的。 A graph property $Υ$ 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 $Υ$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $Υ$ implies $d(u)+d(v)< n+\ell$. Duarte等。 [MFCS 2021]基于解决$（n+\ ell）$的封闭概念，开发了用于共同排行参数化的算法框架 - 对于某些$ \ ell $ b的稳定性，该$ \ ell $稳定，这些$ \ ell $ the con co-degeneracy的功能。在本文中，我们首先确定具有有界周期覆盖的属性的稳定性。之后，结合了Duarte等人的框架。 [MFCS 2021] with some results of Jansen, Kozma, and Nederlof [WG 2019], we obtain a $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$-time algorithm for Minimum Cycle Cover on graphs with co-degeneracy at most $k$, which generalizes Duarte et al. [MFCS 2021]和Jansen等。 [WG 2019]有关哈密顿周期问题的结果。
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 $\ell$ be an integer; the $(n+\ell)$-closure, $\operatorname{cl}_{n+\ell}(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+\ell$ until no such pair remains. A graph property $Υ$ 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 $Υ$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $Υ$ implies $d(u)+d(v)< n+\ell$. 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+\ell)$-stable for some $\ell$ 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^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(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.
