Completely inapproximable monotone and antimonotone parameterized problems

Abstract

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

Conference version in CCC 2010