TY - JOUR
T1 - Turing kernelization for finding long paths and cycles in restricted graph classes
AU - Jansen, B.M.P.
PY - 2017/5
Y1 - 2017/5
N2 - 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.
AB - 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.
KW - Parameterized complexity;
KW - k-PATH
KW - Preprocessing
KW - Turing kernelization
KW - Parameterized complexity
UR - http://www.scopus.com/inward/record.url?scp=85006372269&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2016.10.008
DO - 10.1016/j.jcss.2016.10.008
M3 - Article
VL - 85
SP - 18
EP - 37
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
ER -