Preprocessing of Min Ones Problems: A Dichotomy
From MaRDI portal
Publication:3587416
DOI10.1007/978-3-642-14165-2_55zbMath1288.68132arXiv0910.4518MaRDI QIDQ3587416
Magnus Wahlström, Stefan Kratsch
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0910.4518
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, Solving min ones 2-SAT as fast as vertex cover, Lower bounds on kernelization, Two edge modification problems without polynomial kernels, A completeness theory for polynomial (Turing) kernelization, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints, Constraint Satisfaction Parameterized by Solution Size