论文标题
用于Cagraph Edge编辑的准季度顶点内核
A quasi-quadratic vertex Kernel for Cograph edge editing
论文作者
论文摘要
我们提供$ O（k^2 \ mathrm {log} k）$顶点内核，用于Cograph Edge编辑。这改善了Guillemot，Havet，Paul和Perez [1]发现的立方内核，该内核涉及四个还原规则。我们通过引入T模块的诱发路径的包装来概括它们的规则之一，该路径是t型模块，该模块是模块，直至t边缘修改。关键事实是，大型T模块的编辑不能超过T时，这允许获得接近二次的内核。额外的$ \ mathrm {log} k $ factor似乎很难删除，因为在我们的证明中核心的树上的组合引理中有必要。然而，我们认为应达到二次界限。
We provide a $O(k^2 \mathrm{log} k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra $\mathrm{log} k$ factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.
