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

DOI10.1016/j.jcss.2016.10.008zbMath1356.68099arXiv1402.4718MaRDI 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 complexity; Turing kernelization; preprocessing; \(k\)-Path

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

Related Items

Kernelization of Two Path Searching Problems on Split Graphs, Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor, Parameterized certificate dispersal and its variants, 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 and cycles in restricted graph classes, 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, On the kernelization of split graph problems, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion

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