On some FPT problems without polynomial Turing compressions
type: Item
instance of: scholarly article
title: On some FPT problems without polynomial Turing compressions
author: Weidong Luo
published in: Theoretical Computer Science
publication date: 2022-02-01T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7467480
zbMATH Keywords: Turing compression
zbMATH Keywords: Turing kernelization
zbMATH Keywords: parameterized complexity
zbMATH Keywords: compression
zbMATH Keywords: kernelization
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.12.017
OpenAlex ID: W4200338129
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
cites work: On problems without polynomial kernels
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: New Limits to Classical and Quantum Instance Compression
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Kernel(s) for problems with no kernel
cites work: On the Kernelization Complexity of Colorful Motifs
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
cites work: Turing kernelization for finding long paths and cycles in restricted graph classes
cites work: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
cites work: Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
cites work: Parameterized computational complexity of finding small-diameter subgraphs
cites work: A polynomial Turing-kernel for weighted independent set in bull-free graphs
cites work: A completeness theory for polynomial (Turing) kernelization
cites work: Q4967164
cites work: Lower bounds on kernelization
cites work: Known Algorithms for Edge Clique Cover are Probably Optimal
cites work: On the Parameterized Complexity of Biclique Cover and Partition
cites work: On the complete width and edge clique cover problems
cites work: Clique Cover and Graph Separation
cites work: Computational Complexity
cites work: Relations Among Complexity Measures
cites work: Data reduction and exact algorithms for clique cover
cites work: Q4152571
cites work: Mod/Resc parsimony inference: theory and application
cites work: Block-graph width
cites work: Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
cites work: On the complexity of some colorful problems parameterized by treewidth
cites work: Some results on \((a:b)\)-choosability
cites work: Q5090494
cites work: The complexity landscape of decompositional parameters for ILP
cites work: A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
cites work: Reducibility among Combinatorial Problems
cites work: The complexity of theorem-proving procedures
cites work: Q4256650
cites work: Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
cites work: Does Looking Inside a Circuit Help
cites work: On the complexity of circuit satisfiability
cites work: Which problems have strongly exponential complexity?
cites work: On reductions of NP sets to sparse sets
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Lower bounds for kernelizations and other preprocessing procedures
cites work: Diminishable parameterized problems and strict polynomial kernelization
DOI: 10.1016/J.TCS.2021.12.017
description: scientific article; zbMATH DE number 7467480