篱笆集群删除问题的算法和复杂性
套期保值图是一个图形,其边缘集已被划分为称为对冲的组。 在这里,我们考虑一个众所周知的集群删除问题的概括,命名为Hedge Cluster Deletion。 任务是计算对冲图的最小对冲数,以便它们的移除导致一个与不同步的集团联盟同构的图形。 我们表明,对于包含顶点-脱接的3顶点路径作为子图的有界大小的图形,Hedge Cluster Deletion可以在多项式时间解决。 关于它的近似性,我们证明问题与Min Horn Deletion问题的相关复杂性密切相关,这是一个众所周知的布尔CSP问题。 我们的连接表明,对于任何 ε >0,r 是给定的对冲图中的对冲聚类删除值 2^O(log^1-ε) 的 NP-hard 很难,其中 r 是给定的对冲图中的对冲数。 基于其分类(in)的近似值和几乎所有非平凡图的结构施加的难度,我们考虑对冲底层结构。 我们给出一个多项式时间算法,每当输入图的每个三角形被最多两个对冲覆盖时,Hedge Cluster Deletion的近似值比率。 在达到这一结果的过程中,我们有效解决的一个有趣的成分是Vertex Cover问题的变体,其中除了覆盖边缘集所需的顶点集外,还应将一组给定的顶点约束包含在解决方案中。 此外,作为有效精确算法存在的可能解决方法,我们提出了对冲交叉图,这是篱笆交叉点图,由对冲。 朝这个方向,每当对冲交叉点图是鰰凿图时,我们给出了一个对冲集群删除的多项式时间算法。
数据结构与算法
