一个用于d-击中集的精化核

《Journal of Computer and System Sciences》：A refined kernel for d-Hitting Set

　　•我们改进了d-击中集问题的顶点核大小，将其缩小为(2d?2)kd?1+k。•我们为3-击中集问题和无三角形顶点删除问题分别获得了4k2+k的顶点核。•我们的方法采用线性规划来识别HS冠分解，从而实现这一改进。引言d-击中集问题是理论计算机科学中的一个基本问题，几十年来已在多种算法范式中得到广泛研究。我们首先给出其形式化定义：该问题为众多图修改问题提供了统一的框架。对于任意固定图H，H-自由顶点删除问题（删除k个顶点以消除所有H子图）是|V(H)|-击中集问题的特例。重要特例包括：•顶点覆盖（2-击中集问题，其中H是单个图）。•无三角形顶点删除和簇顶点删除（3-击中集问题，其中H分别为K3和P3）。•d-路径顶点覆盖、d-分量连通度和d-有界度顶点删除。该问题还与描述复杂性有关，其中一阶逻辑片段可归约为d-击中集问题[1]。鉴于其广泛适用性，d-击中集问题已从多个算法角度得到深入研究。我们的工作聚焦于核化结果。经典结果最早于2004年建立[2]，也可通过Erd?s-Rado向日葵引理[3]证明，该结果给出一个具有O(kd)个顶点和超边的核。该界在本质上是紧的，原因如下：命题1 [4]对于任意常数整数d>1，除非co-NP ? NP/poly，否则对于任意?>0，d-击中集问题不存在到大小为O(nd??)实例的多项式时间归约。虽然超边的O(kd)界是最优的，但顶点核界仍有改进空间。Abu-Khzam[5]于2007年取得突破，给出了(2d?1)kd?1+k的顶点核，由于该问题的广泛适用性，这一结果已成为参数化算法中的基石成果。核化领域的一个重大开放问题是：d-击中集问题是否对某个?>0存在O(kd?1??)的顶点核[6], [7], [8], [9], [10]。Fomin等人[10]最近关于有损核化的工作表明，对于任意?>0，d-击中集问题存在一个（随机化的）纯(d?δ)-近似核化协议，产生的核大小为O(k1+?)，其中轮数和δ>0是仅依赖于d和?的常数。主要贡献。在本文中，我们证明d-击中集问题具有至多(2d?2)kd?1+k个顶点的核。特别地，对于d=3，3-击中集问题具有4k2+k个顶点的核。我们的结果改进了先前的界(2d?1)kd?1+k。在先前的算法中，最关键的步骤之一是使用称为HS冠分解的技术来缩减实例规模。相比之下，我们的算法不依赖于分析组合结构来识别HS冠分解，而是采用线性规划方法来计算它们。这种方法使我们能够在更小的超图中找到HS冠分解，最终实现更高效的核。组织结构。第2节首先回顾基本定义并建立符号体系。在第3节中，我们介绍VC冠分解和HS冠分解的概念，它们是算法中的重要工具。第4节给出并分析算法，最终归约规则的证明推迟到第5节。最后，第6节总结全文。章节片段预备知识本文主要关注超图。超图定义为二元组(V,E)，其中V是有限集合，其元素称为顶点，E是超边集合，每条超边是V的子集。如果每条超边至多包含两个顶点，则超图称为简单图；此时超边简称为边。我们用H表示超图，用G表示简单图。输入击中集实例(V,E)被视为HS冠分解经典的冠分解，即VC冠分解，最初是为顶点覆盖问题引入的[12], [13]。在本文中，我们将在超图中使用其变体。为便于参考，我们首先给出简单图上VC冠分解的定义。定义1简单图G=(V,E)的VC冠分解是一对(I,J)，其中I?V且J?V，满足以下性质。1.I是独立集。2.I与V?(I∪J)之间没有边。3.存在一个单射算法框架我们的核化算法包含六个归约规则。在引入一个归约规则时，我们假设所有先前的归约规则不适用于当前实例。如前所述，我们的核化算法是对文献[5]中先前算法的改进，我们首先展示这两种算法之间的差异。参见图3。规则1、2、4和5相同。规则3简单但为本文新添加。主要区别在于引理5在本节中，我们证明引理5并介绍归约规则6中使用的多项式时间算法。对于给定实例(H,k)，我们解决两个问题：（i）在什么条件下可以保证H中存在HS冠分解？（ii）如果存在这样的HS冠分解，在什么条件下可以高效找到它？第一个问题在第5.1节中解决，第二个问题在第5.2节中讨论，同时我们也在那里证明引理5的正确性。结论在本文中，我们针对任意固定d≥3的d-击中集问题给出了改进的顶点核，大小为(2d?2)kd?1+k。具体而言，对于3-击中集问题，我们获得了4k2+k大小的顶点核。由于许多问题通过从d-击中集问题的归约获得其最佳已知顶点核，我们的结果也为若干相关问题（如无三角形顶点删除）提供了改进的顶点核。在我们的算法中，我们利用线性规划来识别HS冠分解。线性规划是解决作者贡献声明刘宇希：撰写—原稿，方法论，形式分析。肖明宇：撰写—审阅与编辑，监督，方法论，资金获取。致谢本工作受国家自然科学基金资助，项目号：62372095、62172077和62350710215。刘宇希|肖明宇