论文标题
用于无爪边缘修饰问题的多项式内核
Polynomial Kernels for Paw-free Edge Modification Problems
论文作者
论文摘要
令$ h $为固定图。给定图形$ g $和一个整数$ k $，$ h $ free Edge修改问题询问是否可以在$ g $中最多可以修改$ k $边缘，以使其$ h $ free。 Sandeep和Sivadasan（IPEC 2015）询问无PAW完成问题和无PAW边缘删除问题是否允许多项式内核。我们通过分别介绍$ O（k）$ - 顶点和$ o（k^4）$ - 顶点内核来肯定地回答两个问题。这是一个正在进行的程序的一部分，旨在了解$ h $ free Edge修改问题的可压缩性。
Let $H$ be a fixed graph. Given a graph $G$ and an integer $k$, the $H$-free edge modification problem asks whether it is possible to modify at most $k$ edges in $G$ to make it $H$-free. Sandeep and Sivadasan (IPEC 2015) asks whether the paw-free completion problem and the paw-free edge deletion problem admit polynomial kernels. We answer both questions affirmatively by presenting, respectively, $O(k)$-vertex and $O(k^4)$-vertex kernels for them. This is part of an ongoing program that aims at understanding compressibility of $H$-free edge modification problems.
