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

DOI10.1016/j.jcss.2016.10.008zbMath1356.68099arXiv1402.4718OpenAlexW1566722385MaRDI QIDQ730497

Bart M. P. Jansen

Publication date: 28 December 2016

Published in: Journal of Computer and System Sciences, Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.4718

zbMATH Keywords

parameterized complexityTuring kernelizationpreprocessing\(k\)-Path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Related Items (11)

On the kernelization of split graph problems ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Parameterized certificate dispersal and its variants ⋮ On some FPT problems without polynomial Turing compressions ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ A completeness theory for polynomial (Turing) kernelization

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Kernel bounds for path and cycle problems
• Lower bounds on kernelization
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Infeasibility of instance compression and succinct PCPs for NP
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Some consequences of non-uniform conditions on uniform classes
• On problems without polynomial kernels
• Parameterized computational complexity of finding small-diameter subgraphs
• Long cycles in 3-connected graphs
• The circumference of a graph with no \(K_{3,t}\)-minor. II
• Pancyclicity and NP-completeness in planar graphs
• A completeness theory for polynomial (Turing) kernelization
• Parametrized complexity theory.
• Fast Witness Extraction Using a Decision Oracle
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• On the Kernelization Complexity of Colorful Motifs
• Kernel(s) for problems with no kernel
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Kernelization: New Upper and Lower Bound Techniques
• Kernelization Lower Bounds by Cross-Composition
• Finding Highly Connected Subgraphs
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• Parameterized certificate dispersal and its variants

This page was built for publication: Turing kernelization for finding long paths and cycles in restricted graph classes