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?
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-hard. Dom, Fellows, and Rosamond [PDF] proved W-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-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.