论文标题
预处理顶点删除问题：通过低级邻接表征图形属性
Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
论文作者
论文摘要
我们考虑$π$ - free删除问题通过顶点盖的大小参数为参数，对于一系列的图形属性$π$。给定输入图$ g $，此问题询问是否有最多有$ k $顶点的子集，其删除可确保所得的图不包含$π$的图形，如诱导的子图。许多顶点删除问题，例如完美的删除，无轮删除和间隔删除符合此框架。我们介绍了通过低级别邻接表征图表属性$π$的概念，并将其用作$π$ free删除的一般内元化定理的基石，该删除由顶点盖的大小进行了参数化。由此产生的框架捕获了诸如免费删除，无轮删除和间隔删除等问题。此外，我们的新框架表明，当通过顶点覆盖物参数化时，到完美图的顶点删除问题具有多项式内核，从而解决了Fomin等人的开放问题。 [JCSS 2014]。我们的主要技术贡献表明，在$ \ mathbb {f} _2 $上适当定义的向量的线性偏置依赖性意味着有关存在禁止诱导子图的存在图理论语句。
We consider the $Π$-free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties $Π$. Given an input graph $G$, this problem asks whether there is a subset of at most $k$ vertices whose removal ensures the resulting graph does not contain a graph from $Π$ as induced subgraph. Many vertex-deletion problems such as Perfect Deletion, Wheel-free Deletion, and Interval Deletion fit into this framework. We introduce the concept of characterizing a graph property $Π$ by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for $Π$-Free Deletion parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-Free Deletion, Wheel-free Deletion, and Interval Deletion. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. [JCSS 2014]. Our main technical contribution shows how linear-algebraic dependence of suitably defined vectors over $\mathbb{F}_2$ implies graph-theoretic statements about the presence of forbidden induced subgraphs.
