Completely inapproximable monotone and antimonotone parameterized problems

DOI10.1016/J.JCSS.2012.09.001MaRDI QIDQ1936258zbMATH OpenOpenAlexFDO

Authors Dániel Marx

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

zbMATH Keywords

circuit satisfiabilitycircuitsfixed-parameter tractabilityinapproximability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function $ho$, unless $FPTeqW[1]$. In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio $ho(OPT)$ for any nontrivial function $ho$.

Recommendations

• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• When is weighted satisfiability FPT?
• Parameterized complexity of weighted satisfiability problems
• Parameterized complexity of constraint satisfaction problems
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting

Cited in

(9)

• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Succinct monotone circuit certification: planarity and parameterized complexity
• Succinct certification of monotone circuits
• When is weighted satisfiability FPT?
• The constant inapproximability of the parameterized dominating set problem
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Complexity of minimum-size arc-inconsistency explanations
• Complete problems for monotone NP
• Parameterized inapproximability of Morse matching

This page was built for publication: Completely inapproximable monotone and antimonotone parameterized problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1936258)