On the kernelization of split graph problems
On the kernelization of split graph problems
复制标题
关于裂图问题的核化
DOI：
10.1016/j.tcs.2017.09.023
复制
发表时间：
2017-09
影响因子：
1.1
通讯作者：
Jiong Guo
中科院分区：
文献类型：
--
作者：
Yongjie Yang;Yash Raj Shrestha;Wenjun Li;Jiong Guo
分裂图是指其顶点可以划分为一个团和一个独立集的图。我们研究了分裂图的许多问题，即k-顶点不相交路、k-圈、k-路和k-稳定集问题。在k-顶点不交路问题中，我们给定一个图和k个顶点的终端对，并询问是否存在一组k个顶点不交路分别连接这些终端对。在k-圈/k-路问题中，我们给出一个图，并询问是否存在长度为k的路/圈。k-稳定集问题以一个图和一个整数k作为输入，并询问该图是否有一个k个顶点的子集，使得该子集中每两个顶点之间的距离至少为k + 1。已知上述问题在分裂图上都是NP-完全的。对于k-顶点不相交路径问题，我们得到了一个4k-顶点核，对于k-路径问题和k-圈问题，我们得到了一个O（k2）-顶点核.对于k-稳定集问题，当k = 1或k ≥ 3时，该问题在分裂图上是多项式时间可解的.当k = 2时，我们证明了分裂图上的k-稳定集问题关于k是W [1]-完全的.然而，如果给定的分裂图不包含K1，r作为导出子图，并且分裂图的独立集中的每个顶点的度至多为d，则我们导出了k-2-Stable Set问题的线性顶点核，其中r和d都是常数.
A split graph is a graph whose vertices can be partitioned into a clique and an independent set. We study numerous problems on split graphs, namely the k-Vertex-Disjoint Paths, k-Cycle, k-Path and k-ℓ-Stable Set problems. In the k-Vertex-Disjoint Paths problem, we are given a graph and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-Cycle/k-Path problem, we are given a graph and are asked whether there is a path/cycle of length k. The k-ℓ-Stable Set problem takes a graph and an integer k as input, and asks whether the graph has a subset of k vertices such that the distance between every two vertices in the subset is at least ℓ+ 1. It is known that all the above problems are NP-complete on split graphs. We derive a 4k-vertex kernel for the k-Vertex-Disjoint Paths problem and an O (k 2)-vertex kernel for both the k-Path problem and the k-Cycle problem. Concerning the k-ℓ-Stable Set problem, for ℓ= 1 or ℓ≥ 3, the problem is polynomial-time solvable on split graphs. For ℓ= 2, we prove that the k-ℓ-Stable Set problem is W [1]-complete on split graphs, with respect to k. However, if the given split graph contains no K 1, r as an induced subgraph, and every vertex in the independent set of the split graph has degree at most d, we derive a linear vertex kernel for the k-2-Stable Set problem, where both r and d are constants.
登录
查看更多内容
DOI：
10.1145/1721837.1721848
发表时间：
2010-03
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Stéphan Thomassé
通讯作者：
Stéphan Thomassé
DOI：
10.1016/j.jcss.2016.10.008
发表时间：
2014-02
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
B. Jansen
通讯作者：
B. Jansen
影响因子：
1.1
作者：
Mingyu Xiao;Hiroshi Nagamochi
通讯作者：
Hiroshi Nagamochi
线性问题核的平面图顶点划分
影响因子：
1.1
作者：
Jianxin Wang;Yongjie Yang;Jiong Guo;Jianer Chen
通讯作者：
Jianer Chen
DOI：
10.2197/ipsjjip.23.239
发表时间：
2014-10
期刊：
ArXiv
影响因子：
--
作者：
Aaron B. Adcock;E. Demaine;M. Demaine;Michael P. O’Brien;F. Reidl;Fernando Sánchez Villaamil;Blair D. Sullivan
通讯作者：
Aaron B. Adcock;E. Demaine;M. Demaine;Michael P. O’Brien;F. Reidl;Fernando Sánchez Villaamil;Blair D. Sullivan