论文标题
利用$ \ mathbf {c} $ - 用于图形问题的内核化算法中关闭
Exploiting $\mathbf{c}$-Closure in Kernelization Algorithms for Graph Problems
论文作者
论文摘要
如果每对具有至少C共同邻居的顶点相邻，则图形是c封闭的。图G的C型是最小的数字，因此G被C封闭。 Fox等。 [ICALP '18]定义了c封闭式并在集团枚举的背景下进行了研究。我们表明，C型可以用于几种经典图形问题中的内核化算法。我们表明，统治集合k^o（c）的内核，诱导匹配的匹配允许具有O（c^7*k^8）顶点的内核，而Inrredimend set seet则在o（c^（5/2）*k^3）的核中允许内核。如我们所示，我们的内核化利用了C封闭图具有多项式结合的Ramsey数字的事实。
A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number such that G is c-closed. Fox et al. [ICALP '18] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^O(c), that Induced Matching admits a kernel with O(c^7*k^8) vertices, and that Irredundant Set admits a kernel with O(c^(5/2)*k^3) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.
