Golpeando conjuntos con una subfamilia

9

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 .FdUHkU1k<d(k,d)FVFWHWV

Dada una colección como anteriormente, el - golpear-set problema es encontrar un más pequeño -hitting set- para .F(k,d)(k,d)HF

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).k=1k=1d3

¿Alguien sabe algún resultado con respecto a la complejidad o la dureza de la aproximación del problema -hit-set con:(k,d)

  1. k=1 y ?d=4
  2. d=4 y ?1<k<d
  3. 1k<d y arbitraria?d
Vicente Helano
fuente

Respuestas:

6

Para una constante el problema del conjunto de golpes no es más difícil que el conjunto original de golpes (es decir, ) en vista de la aproximación y la complejidad parametrizada. Hay una reducción simple de -HS a -HS. Para una instancia del primer problema, obtenemos una instancia de del segundo en el que cada elemento corresponde a un subconjunto de elementos de , y cada conjunto en corresponde a un conjunto en de la misma manera (es decir, mapeando todosd(k,d)dk=1kdd(U,F,d,k)(U,F,d)eUkUFFk subconjuntos de elementos de a elementos en ). Dado que es una constante, el tamaño de la nueva instancia es una función polinómica del tamaño de la primera instancia ( ). Un conjunto de golpes para el primer problema corresponde a un conjunto de golpes de la misma cardinalidad para el segundo problema y viceversa, por lo tanto, la reducción es la preservación de la aproximación.UUkO(nk)

Parham
fuente