On some FPT problems without polynomial Turing compressions

DOI10.1016/J.TCS.2021.12.017MaRDI QIDQ2072079zbMATH OpenOpenAlexFDO

Authors Weidong Luo

Publication date 1 February 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.12.017

zbMATH Keywords

parameterized complexitycompressionkernelizationTuring kernelizationTuring compression

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Linear FPT reductions and computational lower bounds
• On problems without polynomial kernels
• Infeasibility of instance compression and succinct PCPs for NP
• Incompressibility through Colors and IDs
• On Problems without Polynomial Kernels (Extended Abstract)

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1318518 (Why is no real title available?)
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
• A completeness theory for polynomial (Turing) kernelization
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Abusing the Tutte matrix: an algebraic instance compression for the \(K\)-set-cycle problem
• Block-graph width
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Clique Cover and Graph Separation
• Computational Complexity
• Data reduction and exact algorithms for clique cover
• Diminishable parameterized problems and strict polynomial kernelization
• Does looking inside a circuit help?
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel(s) for problems with no kernel
• Kernelization Lower Bounds by Cross-Composition
• Lower bounds for kernelizations and other preprocessing procedures
• Lower bounds on kernelization
• Mod/Resc parsimony inference: theory and application
• New limits to classical and quantum instance compression
• On problems without polynomial kernels
• On reductions of NP sets to sparse sets
• On the Kernelization Complexity of Colorful Motifs
• On the complexity of circuit satisfiability
• On the complexity of some colorful problems parameterized by treewidth
• On the parameterized complexity of biclique cover and partition
• Parameterized algorithms
• Parameterized computational complexity of finding small-diameter subgraphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
• Recent developments in kernelization: a survey
• Reducibility among combinatorial problems
• Relations Among Complexity Measures
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some results on \((a:b)\)-choosability
• The complexity landscape of decompositional parameters for ILP
• The complexity of theorem-proving procedures
• Tight complexity lower bounds for integer linear programming with few constraints
• Turing kernelization for finding long paths in graphs excluding a topological minor
• Which problems have strongly exponential complexity?

Cited in

(2)

• Polynomial Turing compressions for some graph problems parameterized by modular-width
• On the computational hardness based on linear fpt-reductions

This page was built for publication: On some FPT problems without polynomial Turing compressions

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