<p>The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W<a href="http://www.cs.bme.hu/~dmarx/papers/marx-esa2005.pdf">1</a>-hardness for covering points with unit squares. A draft is <a href="http://www.cs.bme.hu/~dmarx/papers/marx-esa2005.pdf">here</a>.</p>

CC BY-SA 3.0
2014-05-19T04:51:36.663Z
There is hardness of k-center clustering if the dimension is high enough.

http://www.cs.bme.hu/~dmarx/papers/cabello-covering-talg.pdf

There are PTASes for some variants of geometric set-cover, so it seems unlikely that it is W[2]-hard for all variants.
Sariel Har-Peled
CC BY-SA 3.0
2014-05-18T13:33:36.080Z
2014-05-18T13:33:36.080Z
someone
<p>Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-15T14:52:27.670Z
What is W[2] hardness?
Vivek Bagaria
CC BY-SA 3.0
2014-05-19T23:13:15.903Z
@Bagaria See [W hierarchy](http://en.wikipedia.org/wiki/Parameterized_complexity#W_hierarchy), and may be before that reading [this](http://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems/11773#11773) roughly explanation is easier.
Saeed
<reference-request><cg.comp-geom><parameterized-complexity>
parameterized algorithms for geometric set cover
pradeesha ashok
# parameterized algorithms for geometric set cover

(Asked by: username_0 on 2014-04-11)

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.

**Tags:** reference-request, cg.comp-geom, parameterized-complexity

> **Comments:**
> **username_1**: What is W[2] hardness?  
> **username_2**: @Bagaria See [W hierarchy](http://en.wikipedia.org/wiki/Parameterized_complexity#W_hierarchy), and may be before that reading [this](http://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems/11773#11773) roughly explanation is easier.  

---

## 1 answers

### Answer by username_3 on 2014-05-18. Score: 5 | Accepted answer

The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W[1](http://www.cs.bme.hu/~dmarx/papers/marx-esa2005.pdf)-hardness for covering points with unit squares. A draft is [here](http://www.cs.bme.hu/~dmarx/papers/marx-esa2005.pdf).

> **Comments:**
> **username_4**: There is hardness of k-center clustering if the dimension is high enough.  http://www.cs.bme.hu/~dmarx/papers/cabello-covering-talg.pdf  There are PTASes for some variants of geometric set-cover, so it seems unlikely that it is W[2]-hard for all variants.  

---

