38
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Great question! $\endgroup$
    – András Salamon
    Commented Aug 17, 2010 at 17:58

3 Answers 3

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

The paper Dániel Marx: Efficient Approximation Schemes for Geometric Problems?. ESA 2005: 448-459 is quite relevant.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.