Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?

It is known that set cover problem is $W[2]$ hard when parametrized by the solution size? There might be some advantages when the sets are defined by geometric objects.

  • $\begingroup$ What is W[2] hardness? $\endgroup$ Apr 15, 2014 at 14:52
  • $\begingroup$ @Bagaria See W hierarchy, and may be before that reading this roughly explanation is easier. $\endgroup$
    – Saeed
    May 19, 2014 at 23:13

1 Answer 1


The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W1-hardness for covering points with unit squares. A draft is here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.