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

DOI10.4230/LIPICS.IPEC.2017.23zbMATH Open1443.68133OpenAlexW2964190780MaRDI QIDQ5111882FDOQ5111882

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/

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

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)

Cites Work

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

Cited In (3)

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

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)