Turing kernelization for finding long paths in graphs excluding a topological minor

DOI10.4230/LIPICS.IPEC.2017.23MaRDI QIDQ5111882zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8557/pdf/LIPIcs-IPEC-2017-23.pdf/

zbMATH Keywords

\(k\)-pathlong pathmodulatorTuring kernelexcluded topological minor

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Turing kernelization for finding long paths in graph classes excluding a topological minor
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Kernel bounds for path and cycle problems

Cites work

• A completeness theory for polynomial (Turing) kernelization
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• Finding highly connected subgraphs
• Graph minors. XVII: Taming a vortex
• Kernel(s) for problems with no kernel
• Kernelization Lower Bounds by Cross-Composition
• Kernelization using structural parameters on sparse graph classes
• Linear connectivity forces large complete bipartite minors: an alternative approach
• Minimum bisection is fixed parameter tractable
• Parameterized algorithms for deletion to \((r,\ell)\)-graphs
• Parameterized certificate dispersal and its variants
• Parameterized computational complexity of finding small-diameter subgraphs
• Some Theorems on Abstract Graphs
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The circumference of a graph with no \(K_{3,t}\)-minor. II
• Turing kernelization for finding long paths in graph classes excluding a topological minor

Cited in

(2)

• Turing kernelization for finding long paths in graph classes excluding a topological minor
• On some FPT problems without polynomial Turing compressions

This page was built for publication: Turing kernelization for finding long paths in graphs excluding a topological minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111882)