论文标题
H-Free边缘修饰问题的不可压缩性：迈向二分法
Incompressibility of H-free edge modification problems: Towards a dichotomy
论文作者
论文摘要
给定图形$ g $和一个整数$ k $，$ h $ free边缘编辑问题是找到$ g $中的最多$ k $的顶点是否存在，以便在$ g $中更改$ g $的毗邻，而没有任何诱导的$ h $。 $ H $ Free Edge编辑的多项式内核的存在在参数化的复杂性文献中受到了极大的关注。众所周知，非平凡的多项式内核在某些图中具有$ h $，最多为4个顶点，但是从5个顶点开始，只有$ h $是完整或空的，才知道多项式内核。这表明，至少没有其他5个顶点的$ H $的猜想是$ h $ free Edge Editing承认多项式内核。为了实现这一目标，我们获得了九个5个5个vertex图的集合$ \ MATHCAL {h} $，以至于每$ h \ in \ nathcal {h} $，$ h $ free-free边缘编辑不可压缩性不可压缩性$ np $ np \ np \ np not \ not $ np $ np ynoply $ hort $ $ h $ - 既不完整也不空的顶点。也就是说，证明这九个图的不可压缩性将对每$ H $ a $ h $ free Edge编辑的内核复杂性进行完整的分类，至少具有5个顶点。 我们也以$ h $ free Edge删除的方式获得类似的结果。由于存在另一个无限的图形$ h $，因此在这里，图片更加复杂。我们获得了一个较大的集合$ \ MATHCAL {H} $，其不可压缩性将对每个图$ H $ to Compressization niranization Complactition均具有至少5个顶点的$ H $ Free Edge Deletion的完整分类。通过简单补充，$ H $ Free Edge完成问题的类似结果也随之而来。
Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to find whether there exists at most $k$ pairs of vertices in $G$ such that changing the adjacency of the pairs in $G$ results in a graph without any induced copy of $H$. The existence of polynomial kernels for $H$-free Edge Editing received significant attention in the parameterized complexity literature. Nontrivial polynomial kernels are known to exist for some graphs $H$ with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if $H$ is either complete or empty. This suggests the conjecture that there is no other $H$ with at least 5 vertices were $H$-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge Editing is incompressible and the complexity assumption $NP \not\subseteq coNP/poly$ holds, then $H$-free Edge Editing is incompressible for every graph $H$ with at least five vertices that is neither complete nor empty. That is, proving incompressibility for these nine graphs would give a complete classification of the kernelization complexity of $H$-free Edge Editing for every $H$ with at least 5 vertices. We obtain similar result also for $H$-free Edge Deletion. Here the picture is more complicated due to the existence of another infinite family of graphs $H$ where the problem is trivial (graphs with exactly one edge). We obtain a larger set $\mathcal{H}$ of nineteen graphs whose incompressibility would give a complete classification of the kernelization complexity of $H$-free Edge Deletion for every graph $H$ with at least 5 vertices. Analogous results follow also for the $H$-free Edge Completion problem by simple complementation.
