loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 IEEE 23rd Annual Conference on Computational Complexity
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard
June 22-June 26
ISBN: 978-0-7695-3169-4
We prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. Our result answers a question of Alekhnovich and Razborov, who proved that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable 2-approximation algorithm unless every problem in W[P] can be solved by a randomized fpt algorithm and asked whether their result can be derandomized. Alekhnovich and Razborov used their inapproximability result as a lemma for proving that resolution is not automatizable unless W[P] is contained in randomized FPT. It is an immediate consequence of our result that the complexity theoretic assumption can be weakened to W[P] =!= FPT. The decision version of the monotone circuit satisfiability problem is known to be complete for the class W[P]. By reducing them to the monotone circuit satisfiability problem with suitable approximation preserving reductions, we prove similar inapproximability results for all other natural minimisation problems known to be W[P]-complete.
Index Terms:
parameterized complexity, inapproximability, derandomisation
Citation:
Kord Eickmeyer, Martin Grohe, Magdalena Gr?, "Approximation of Natural W[P]-Complete Minimisation Problems Is Hard," ccc, pp.8-18, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.