A completeness theory for polynomial (Turing) kernelization
type: Item
instance of: scholarly article
title: A completeness theory for polynomial (Turing) kernelization
zbMATH Open document ID: 1312.68102
author: Danny Hermelin
author: Stefan Kratsch
author: Karolina Sołtys
author: Magnus Wahlström
author: Xi Wu
published in: Algorithmica
publication date: 2015-05-04T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6432669
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: Turing kernelization
zbMATH Keywords: complexity hierarchies
MaRDI profile type: MaRDI publication profile
full work available at URL: s00453-014-9910-8
OpenAlex ID: W2008912593
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: Color-coding
cites work: Kernel(s) for problems with no kernel
cites work: On problems without polynomial kernels
cites work: Kernel bounds for path and cycle problems
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Nondeterminism within $P^ * $
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: The Turing way to parameterized complexity
cites work: On Problems as Hard as CNF-SAT
cites work: Q5743378
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Incompressibility through Colors and IDs
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Parametrized complexity theory.
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
cites work: Parameterized complexity of vertex deletion into perfect graph classes
cites work: Q5743381
cites work: Turing kernelization for finding long paths and cycles in restricted graph classes
cites work: Q4142699
cites work: Q5743382
cites work: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
cites work: Preprocessing of Min Ones Problems: A Dichotomy
cites work: Q5743380
cites work: Two edge modification problems without polynomial kernels
cites work: The parameterized complexity of unique coverage and its variants
cites work: Vertex packings: Structural properties and algorithms
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Some consequences of non-uniform conditions on uniform classes
DOI: 10.1007/S00453-014-9910-8
description: scientific article; zbMATH DE number 6432669