Complexité paramétrée de l'ensemble de frappe dans une dimension VC finie

Je m'intéresse à la complexité paramétrée de ce que j'appellerai le problème d'ensemble d-dimensionnel: donné un espace de plage (c'est-à-dire un ensemble système / hypergraphe) S = (X, R) ayant une dimension VC au plus d et a entier positif k, X contient-il un sous-ensemble de taille k qui touche toutes les plages de R? La version paramétrée du problème est paramétrée par k.

Pour quelles valeurs de d est le problème d-Dimensional Hitting Set

• en FPT?
• dans W [1]?
• W [1] -hard?
• W [2] -hard?

Ce que je sais peut être résumé comme suit:

• 1-Dimensional Hitting Set est en P et donc en FPT. Si S a la dimension 1, il n’est pas difficile de démontrer qu’il existe un ensemble de frappes de taille 2 ou que la matrice d’incidence de S est totalement équilibrée. Dans les deux cas, nous pouvons trouver un jeu minimum de frappes en temps polynomial.

• L'ensemble de frappe à 4 dimensions est W [1] -hard. Dom, Fellows et Rosamond [PDF] ont prouvé la dureté W [1] du problème de la perforation de rectangles parallèles aux axes dans R ^ 2 avec des lignes parallèles aux axes. Ceci peut être formulé en tant que jeu de frappe dans un espace de plage de VC-dimension 4.

• Si aucune restriction n'est placée sur d, alors nous avons le problème standard de jeu de frappe qui est W [2] -complete et NP-complete.

• Langerman et Morin [citeseer link] fournissent des algorithmes FPT pour Set Cover en dimension restreinte, bien que leur modèle de dimensionnalité lié ne soit pas identique à celui défini par la dimension VC liée. Leur modèle ne semble pas inclure, par exemple, le problème de frapper des demi-espaces avec des points, bien que le problème du prototype de leur modèle équivaut à frapper des hyperplans avec des points.

Je pense que ce problème est trop difficile. Nous ne connaissons pas la réponse à des problèmes beaucoup plus faciles dans cette famille. Par exemple, étant donné un ensemble de n points dans le plan et un ensemble de (disons n) unités de disque, déterminez s’il existe une couverture des points par k des unités de disque. Il existe un algorithme simple n ^ O (k) time pour cela, et je ne serais pas surpris si vous utilisez des connaissances connues, vous pouvez faire n ^ O (sqrt {k}) (mais même cela n’est pas évident), mais f ( k) * n ^ {O (1)} est ouvert et serait en fait très intéressant. Une approximation (1 + eps) découle des travaux de Mustafa et Ray http://portal.acm.org/citation.cfm?id=1542362.1542367 .

BTW, pour la version continue où n’importe quel disque est permis, on peut résoudre le problème en n ^ {O (k)} temps. Dans ce cas, un PTAS est également assez facile à utiliser avec des grilles décalées.

Nous abordons cette question dans une nouvelle pré-impression: http://arxiv.org/abs/1512.00481

Frapper Ensemble dans des hypergraphes de faible dimension VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).

Il s'avère que Frapper Set est déjà dur [1] lorsque la dimension VC est égale à 2.

Le document Dániel Marx: Schémas d’approximation efficaces pour des problèmes géométriques ?. SEC 2005: 448-459 est tout à fait pertinent.