Trovare un set di colpi di dimensioni N/2 NP-Hard?

Question

Nel colpire il problema del set ci viene data una raccolta E di sottoinsiemi di V e vogliamo trovare il sottoinsieme più piccolo di V che interseca (colpi) ogni set in E.

Nella versione decisionale del problema, ci viene chiesto se esiste un set di dimensioni colpite al massimo K.

Questo problema è noto per essere np-hard. Tuttavia, mi chiedo se il problema sia ancora in duro quando viene chiesto se esiste un set da colpire la cui dimensione è strettamente inferiore a n/2, cioè, al massimo n/2 - 1, (dove n è la dimensione di V) .

Attualmente sto lavorando a un altro problema e sono convinto che il problema sia np-hard. Quindi sto cercando di trovare una riduzione. Mi sono reso conto che se il problema di cui sopra è np-hard, allora ho finito.

Qualsiasi aiuto è apprezzato.