论文标题
TreeWidth-2顶点删除的核心化
Kernelization for Treewidth-2 Vertex Deletion
论文作者
论文摘要
TreeWidth-2顶点删除问题询问是否可以从图形中删除一组最多的$ T $顶点，以使所得的图最多具有两个。当且仅当它不包含$ k_4 $ binor时，图最多具有两个。因此，此问题对应于NP-HARD $ \ MATHCAL {F} $ - $ \ MATHCAL {F} = \ {K_4 \} $的小封面问题。对于$ \ MATHCAL {F} $的任何变体 - $ \ Mathcal {F} $包含平面图的次要封面问题，众所周知，多项式内核存在。即，在多项式时间内输出一个大小$ t^{o（1）} $的等效实例的预处理例程。但是，此证明是非构造性的，这意味着此证明不会在内核大小上产生明确的绑定。 $ \ {k_4 \} $ - 次要封面问题是$ \ mathcal {f} $的最简单变体 - 少量封面问题，其核大小未知。 为了开发一种建设性的内核化算法，我们提出了一种将图形分解为近乎主要累及的新方法，以便可以使用基本还原规则来减少这种新分解中的近核心。我们的方法扩展了Van Bevern等人的“近似和整洁”框架。 [Algorithmica 2012]提供的保证比该框架和常规突出分解所提供的保证更强大。此外，我们提供了$ \ {k_4，k_ {2,3} \} $的基本还原规则的扩展 - 唐克斯等人引入的次要封面kernelization算法。 [IPEC 2021]。 使用新的分解方法和还原规则，我们获得了由$ o（t^{41}）$ Vertices组成的内核，这是第一个建设性内核。该内核是迈向更具体的内核化范围的一步，用于$ \ Mathcal {f} $ - 较小的封面问题，其中$ \ Mathcal {f} $包含平面图，我们的分解为实现这些新界限提供了潜在的方向。
The Treewidth-2 Vertex Deletion problem asks whether a set of at most $t$ vertices can be removed from a graph, such that the resulting graph has treewidth at most two. A graph has treewidth at most two if and only if it does not contain a $K_4$ minor. Hence, this problem corresponds to the NP-hard $\mathcal{F}$-Minor Cover problem with $\mathcal{F} = \{K_4\}$. For any variant of the $\mathcal{F}$-Minor Cover problem where $\mathcal{F}$ contains a planar graph, it is known that a polynomial kernel exists. I.e., a preprocessing routine that in polynomial time outputs an equivalent instance of size $t^{O(1)}$. However, this proof is non-constructive, meaning that this proof does not yield an explicit bound on the kernel size. The $\{K_4\}$-Minor Cover problem is the simplest variant of the $\mathcal{F}$-Minor Cover problem with an unknown kernel size. To develop a constructive kernelization algorithm, we present a new method to decompose graphs into near-protrusions, such that near-protrusions in this new decomposition can be reduced using elementary reduction rules. Our method extends the `approximation and tidying' framework by van Bevern et al. [Algorithmica 2012] to provide guarantees stronger than those provided by both this framework and a regular protrusion decomposition. Furthermore, we provide extensions of the elementary reduction rules used by the $\{K_4, K_{2,3}\}$-Minor Cover kernelization algorithm introduced by Donkers et al. [IPEC 2021]. Using the new decomposition method and reduction rules, we obtain a kernel consisting of $O(t^{41})$ vertices, which is the first constructive kernel. This kernel is a step towards more concrete kernelization bounds for the $\mathcal{F}$-Minor Cover problem where $\mathcal{F}$ contains a planar graph, and our decomposition provides a potential direction to achieve these new bounds.
