The K-way vertex cut problem} consists in, given a graph G, finding a subset of vertices of a given size, whose removal partitions G into the maximum number of connected components. This problem has many applications in several areas. It has been proven to be NP-complete on general graphs, as well as on split and planar graphs. In this paper, we enrich its complexity study with two new results. First, we prove that it remains NP-complete even when restricted on the class of bipartite graphs. This is unlike what it is expected, given that the K-way vertex cut problem is a generalization of the Maximum Independent set problem which is polynomially solvable on bipartite graphs. We also provide its equivalence to the wellknown problem, namely the Critical Node Problem (CNP), On split graphs. Therefore, any solving algorithm for the CNP on split graphs is a solving algorithm for the K-way vertex cut problem and vice versa.
翻译：Kway 顶点切除问题} 包括, 给一个图形 G, 找到一个特定大小的顶点子子子, 其除去分区 G 进入最大连接组件数 。 这个问题在多个区域有许多应用 。 这个问题在一般图形以及分裂和平面图上已经证明是完整的 NP 。 在本文中, 我们用两个新结果丰富其复杂程度的研究 。 首先, 我们证明它仍然是 NP- 完整的, 即使限制在双面图形类中 。 这与预期的不一样, 因为 Kway 顶点切断问题是双面图上可多线性软化的最大独立设置问题的一般化 。 我们还提供了它与众所周知的问题的等同性, 即关键节点问题( CNP ) 、 分裂图 。 因此, 分面图上 CNP 的任何解算法都是 K- way 顶点切问题和反向问题的解算法 。
相关内容
微信扫码咨询专知VIP会员