# 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?
• W-hard?
• W-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-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.

• Great question! Aug 17, 2010 at 17:58