On some FPT problems without polynomial Turing compressions
From MaRDI portal
Publication:2072079
DOI10.1016/J.TCS.2021.12.017OpenAlexW4200338129MaRDI QIDQ2072079
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
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Mod/Resc parsimony inference: theory and application
- Lower bounds on kernelization
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Block-graph width
- Lower bounds for kernelizations and other preprocessing procedures
- Infeasibility of instance compression and succinct PCPs for NP
- On the complexity of some colorful problems parameterized by treewidth
- Solving MAX-\(r\)-SAT above a tight lower bound
- On the complete width and edge clique cover problems
- Turing kernelization for finding long paths and cycles in restricted graph classes
- Some results on \((a:b)\)-choosability
- On problems without polynomial kernels
- On reductions of NP sets to sparse sets
- Which problems have strongly exponential complexity?
- Diminishable parameterized problems and strict polynomial kernelization
- The complexity landscape of decompositional parameters for ILP
- Parameterized computational complexity of finding small-diameter subgraphs
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
- A completeness theory for polynomial (Turing) kernelization
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- On the complexity of circuit satisfiability
- Clique Cover and Graph Separation
- Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
- On the Kernelization Complexity of Colorful Motifs
- Kernel(s) for problems with no kernel
- New Limits to Classical and Quantum Instance Compression
- Known Algorithms for Edge Clique Cover are Probably Optimal
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Relations Among Complexity Measures
- Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
- On the Parameterized Complexity of Biclique Cover and Partition
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Does Looking Inside a Circuit Help
- Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
- Computational Complexity
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Data reduction and exact algorithms for clique cover
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- The complexity of theorem-proving procedures
This page was built for publication: On some FPT problems without polynomial Turing compressions
