首页> 外文期刊>Algorithmica >Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
【24h】

Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

机译:寻找有界度的削减:复杂性,FPT和精确算法,以及内核

获取原文
获取原文并翻译 | 示例

摘要

A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [Discrete Applied Mathematics, 2020], we introduce a natural generalization of this problem, which we call d -Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d -Cut on (2d + 2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d + 2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [DAM, 2020], is a polynomial kernel for d -Cut for every positive integer d, parameterized by the vertex deletion distance of the input graph to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O*(2(n)).
机译:匹配切口是图形的顶点组的分隔,分为两个组A和B,使得每个顶点在切割的另一侧的大多数邻居处具有。匹配的剪切问题询问图表是否具有匹配的切割,并在文献中进行了集中研究。被Komusiewicz等人提出的问题为动机。 [离散应用数学,2020],我们介绍了这个问题的自然概括,我们呼叫D -cut:对于正整数D,D-Cut是图形的顶点组的两分为两组A和B这样,每个顶点都在切割的大多数d邻居中。我们概括(在某些情况下,改进)匹配削减问题的一些结果。即,我们从(2D + 2)-Cut上的NP硬度降低(2D + 2) - 一个曲线图和最大程度最大程度的图形算法,最多d + 2。硬度结果中的度数不太可能得到改善,因为它将在内部分区的背景下反驳长期猜想。然后,我们提供了几个参数的FPT算法:将切割,树木宽,群集距离交叉的最大边缘数以及与CO-Cluster距离的距离。特别地,树木宽度算法改善了用于匹配切割的最佳已知算法的运行时间。我们的主要技术贡献,建立了Komusiewicz等的技术。 [DAM,2020],是用于每个正整数D的多项式内核,通过将输入图的顶点删除距离参数化为簇图。我们还通过交叉切割的边缘的数量同时参数化,排除多项式内核的存在,树木宽度和最大程度。最后,我们提供了一个精确的指数算法,比在时间O *(2(n))中运行的天真的蛮力方法稍微快速。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号