Polynomial Turing compressions for some graph problems parameterized by modular-width

DOI10.1016/J.IC.2025.105355MaRDI QIDQ6884316zbMATH OpenFDO

Authors Weidong Luo

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105355

zbMATH Keywords

fixed-parameter tractabilitymodular widthstructural graph parameterTuring compressionTuring kernel

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• A completeness theory for polynomial (Turing) kernelization
• A hierarchy of polynomial kernels
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A survey of the algorithmic aspects of modular decomposition
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Faster algorithms on branch and clique decompositions
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 7803590 (Why is no real title available?)
• scientific article; zbMATH DE number 7803599 (Why is no real title available?)
• Independent set reconfiguration parameterized by modular-width
• Kernelization Lower Bounds by Cross-Composition
• Linear time solvable optimization problems on graphs of bounded clique-width
• On Problems without Polynomial Kernels (Extended Abstract)
• On some FPT problems without polynomial Turing compressions
• On the Kernelization Complexity of Colorful Motifs
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Parameterized computational complexity of finding small-diameter subgraphs
• Preprocessing complexity for some graph problems parameterized by structural parameters
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Towards exact structural thresholds for parameterized complexity
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Upper bounds to the clique width of graphs

This page was built for publication: Polynomial Turing compressions for some graph problems parameterized by modular-width

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