Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP

DOI10.1007/s00453-011-9559-5zbMath1236.68097MaRDI QIDQ2429346

Stefan Kratsch

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9559-5

zbMATH Keywords

combinatorial optimization; parameterized complexity; kernelization

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)