Turing kernelization for finding long paths and cycles in restricted graph classes
Turing kernelization for finding long paths and cycles in restricted graph classes
复制标题
DOI：
10.1016/j.jcss.2016.10.008
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
B. Jansen
中科院分区：
文献类型：
--
作者：
B. Jansen
K-路问题是指一个给定的无向图是否有一条长度为k的(简单)路。我们证明了当k-路被限制在平面图、有界度图、无爪图或K3，t-无子图上时，k-路具有多项式大小的图灵核。这意味着，有一种算法，在给定属于这些图类之一的k路径实例(G，k)的情况下，当被给予访问在单个步骤中求解大小为k的多项式的k路径实例的神谕时，在多项式时间内计算其答案。我们的技巧也适用于k-圈，它要求至少有一个长度为k的圈。
The k-Path problem asks whether a given undirected graph has a (simple) path of length k. We prove that k-Path has polynomial-size Turing kernels when restricted to planar graphs, graphs of bounded degree, claw-free graphs, or to K 3, t-minor-free graphs. This means that there is an algorithm that, given a k-Path instance (G, k) belonging to one of these graph classes, computes its answer in polynomial time when given access to an oracle that solves k-Path instances of size polynomial in k in a single step. Our techniques also apply to k-Cycle, which asks for a cycle of length at least k.