Sea una familia de subconjuntos de elementos de un universo finito de objetos. Una familia de subconjuntos -elemento de , con , es una - hitting-set de si, para cada existe al menos un conjunto tales que .
Dada una colección como anteriormente, el - golpear-set problema es encontrar un más pequeño -hitting set- para .
Cuando tenemos el problema estándar de conjunto de golpes, y hay muchos resultados anteriores para ello. Sé de análisis parametrizados para el caso con y (ver Brankovic y Fernau , por ejemplo).
¿Alguien sabe algún resultado con respecto a la complejidad o la dureza de la aproximación del problema -hit-set con:
- y ?
- y ?
- y arbitraria?