Parameterized complexity of Hitting Set in finite VC-dimension 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] 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] 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.
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.