Completely inapproximable monotone and antimonotone parameterized problems
From MaRDI portal
Publication:1936258
DOI10.1016/j.jcss.2012.09.001zbMath1261.68066arXiv1711.03886OpenAlexW2077451547MaRDI QIDQ1936258
Publication date: 21 February 2013
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.03886
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Finding disjoint paths on edge-colored graphs: more tractability results, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Complexity of minimum-size arc-inconsistency explanations, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, The Constant Inapproximability of the Parameterized Dominating Set Problem, Succinct certification of monotone circuits, Succinct monotone circuit certification: planarity and parameterized complexity