Turing kernelization for finding long paths and cycles in restricted graph classes

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)18-37
Number of pages20
JournalJournal of Computer and System Sciences
Volume85
DOIs
Publication statusPublished - May 2017

Keywords

  • Parameterized complexity;
  • k-PATH
  • Preprocessing
  • Turing kernelization
  • Parameterized complexity

Fingerprint Dive into the research topics of 'Turing kernelization for finding long paths and cycles in restricted graph classes'. Together they form a unique fingerprint.

  • Cite this