<p>I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there is a cover of the points by k of the unit disks. There is an easy n^O(k) time algorithm for this, and I would not be surprised if using known insights one can do n^O(sqrt{k}) (but even that is not obvious), but doing f(k)*n^{O(1)} is open, and in fact would be quite interesting. A (1+eps) approximation follows from the work of Mustafa and Ray <a href="http://portal.acm.org/citation.cfm?id=1542362.1542367">http://portal.acm.org/citation.cfm?id=1542362.1542367</a>.</p>

<p>BTW, for the continuous version where any unit disk is allowed, one can solve the problem in n^{O(k)} time. A PTAS in this case is also pretty easy using shifted grids. </p>

CC BY-SA 2.5
2010-08-31T21:16:23.260Z
2010-08-31T21:16:23.260Z
Sariel Har-Peled
<p>We address this question in a new preprint:
<a href="http://arxiv.org/abs/1512.00481" rel="noreferrer">http://arxiv.org/abs/1512.00481</a></p>

<p>Hitting Set in hypergraphs of low VC-dimension (Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy). </p>

<p>It turns out that Hitting Set is W[1]-hard already when the VC-dimension is equal to 2.</p>

CC BY-SA 3.0
2015-12-03T08:36:54.100Z
2015-12-03T08:36:54.100Z
László Kozma
<p>The paper Dániel Marx: <a href="http://dx.doi.org/10.1007/11561071_41" rel="nofollow">Efficient Approximation Schemes for Geometric Problems</a>?. ESA 2005: 448-459 is quite relevant.</p>

CC BY-SA 2.5
2011-01-24T20:11:36.997Z
2011-01-26T01:13:26.590Z
2011-01-26T01:13:26.590Z
someone
<p>I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and a positive integer k, does X contain a subset of size k that hits every range in R?  The parameterized version of the problem is parameterized by k.</p>

<p>For what values of d is the d-Dimensional Hitting Set problem</p>

<ul>
<li>in FPT?</li>
<li>in W[1]?</li>
<li>W[1]-hard?</li>
<li>W[2]-hard?</li>
</ul>

<p>What I know can be summarized as follows:</p>

<ul>
<li><p>1-Dimensional Hitting Set is in P and is therefore in FPT.  If S has dimension 1 then it is not difficult to show that either there is a hitting set of size 2 or the incidence matrix of S is totally balanced.  In either case we can find a minimum hitting set in polynomial time.</p></li>
<li><p>4-Dimensional Hitting Set is W[1]-hard.  Dom, Fellows, and Rosamond <a href="http://theinf1.informatik.uni-jena.de/publications/DFR09_s.pdf">[PDF]</a> proved W[1]-hardness for the problem of stabbing axis-parallel rectangles in R^2 with axis-parallel lines.  This can be formulated as Hitting Set in a range space of VC-dimension 4.</p></li>
<li><p>If no restriction is placed on d then we have the standard Hitting Set problem which is W[2]-complete and NP-complete.</p></li>
<li><p>Langerman and Morin <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.152.8053">[citeseer link]</a> give FPT algorithms for Set Cover in restricted dimension, though their bounded dimensionality model is not the same as the model defined by bounded VC-dimension. Their model does not seem to include, for example, the problem of hitting halfspaces with points, though the prototype problem for their model is equivalent to hitting hyperplanes with points.</p></li>
</ul>

CC BY-SA 2.5
2010-08-17T17:58:15.877Z
Great question!
András Salamon
<cc.complexity-theory><cg.comp-geom><set-cover><parameterized-complexity><vc-dimension>
Parameterized complexity of Hitting Set in finite VC-dimension
James King
# Parameterized complexity of Hitting Set in finite VC-dimension

(Asked by: username_0 on 2010-08-17)

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and a positive integer k, does X contain a subset of size k that hits every range in R? The parameterized version of the problem is parameterized by k.

For what values of d is the d-Dimensional Hitting Set problem

* in FPT?
* in W[1]?
* W[1]-hard?
* W[2]-hard?

What I know can be summarized as follows:

* 1-Dimensional Hitting Set is in P and is therefore in FPT. If S has dimension 1 then it is not difficult to show that either there is a hitting set of size 2 or the incidence matrix of S is totally balanced. In either case we can find a minimum hitting set in polynomial time.
* 4-Dimensional Hitting Set is W[1]-hard. Dom, Fellows, and Rosamond [[PDF]](http://theinf1.informatik.uni-jena.de/publications/DFR09_s.pdf) proved W[1]-hardness for the problem of stabbing axis-parallel rectangles in R^2 with axis-parallel lines. This can be formulated as Hitting Set in a range space of VC-dimension 4.
* If no restriction is placed on d then we have the standard Hitting Set problem which is W[2]-complete and NP-complete.
* Langerman and Morin [[citeseer link]](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.152.8053) give FPT algorithms for Set Cover in restricted dimension, though their bounded dimensionality model is not the same as the model defined by bounded VC-dimension. Their model does not seem to include, for example, the problem of hitting halfspaces with points, though the prototype problem for their model is equivalent to hitting hyperplanes with points.

**Tags:** cc.complexity-theory, cg.comp-geom, set-cover, parameterized-complexity, vc-dimension
> **Comments:**
> **username_1**: Great question!  

---

## 3 answers

### Answer by username_2 on 2010-08-31. Score: 14

I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there is a cover of the points by k of the unit disks. There is an easy n^O(k) time algorithm for this, and I would not be surprised if using known insights one can do n^O(sqrt{k}) (but even that is not obvious), but doing f(k)\*n^{O(1)} is open, and in fact would be quite interesting. A (1+eps) approximation follows from the work of Mustafa and Ray <http://portal.acm.org/citation.cfm?id=1542362.1542367>.

BTW, for the continuous version where any unit disk is allowed, one can solve the problem in n^{O(k)} time. A PTAS in this case is also pretty easy using shifted grids.


---

### Answer by username_3 on 2015-12-03. Score: 5

We address this question in a new preprint:
<http://arxiv.org/abs/1512.00481>

Hitting Set in hypergraphs of low VC-dimension (Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy).

It turns out that Hitting Set is W[1]-hard already when the VC-dimension is equal to 2.


---

### Answer by username_4 on 2011-01-24. Score: 3

The paper Dániel Marx: [Efficient Approximation Schemes for Geometric Problems](http://dx.doi.org/10.1007/11561071_41)?. ESA 2005: 448-459 is quite relevant.


---

