Copertura imposta in cui sono consentiti solo alcuni sottoinsiemi speciali

Question

Sto cercando di risolvere un problema che risulta essere una forma del problema di copertura impostata. Ho implementato l'algoritmo di approssimazione della copertura impostata avida per la copertura impostata, ma risulta non essere abbastanza accurato per le mie esigenze.

In particolare ho un elenco fisso, finito, di set speciali e sto cercando di creare una funzione che quando viene fornita un set restituisce l'elenco più piccolo di set speciali che coprono questo set e tale elenco non dovrebbe contenere set che contengono elementi non in Quel set dato. L'elenco fisso sembra che dovrebbe semplificare il problema rispetto alla copertura impostata, ma non sono sicuro di come il requisito aggiuntivo di nessun elemento extra influisca sulla difficoltà. I miei set hanno anche una dimensione massima nota che dovrebbe anche rendere questo più facile da risolvere.

Una versione giocattolo del problema è la seguente:

Permettere $ U $ essere il set $ {a, b, c, d, e, f, g, h } $. Tutti i set che menzioniamo da qui in poi saranno sottoinsiemi di questo set.

Permettere $ S $ essere un elenco di set speciali. Per questa versione del problema possiamo utilizzare il seguente elenco:

$$ s = [ {a, b, c, d, e, f, g, h }, {a, b, c, d }, {e, f, g, h }, {a, e }, {b, f }, {c, g }, {d, h }, {a, b }, {b, c }, {c , d }, {d, e }, {e, f }, {f, g }, {g, h }, {a }, {b }, {c }, {d }, {e }, {f }, {g }, {H }] $$

Per un determinato set $ G $ Qual è l'elenco più piccolo di set che fanno parte $ S $ quale copertura $ G $, (ecco dove si trova l'unione dei set nell'elenco $ G $).

Per il problema dei giocattoli di cui sopra, l'avide approssimazione che ho implementato, se presentata con un set come $ {b, c, g, h } $, produce $ [ {c, g }, {b }, {h }] $ Invece dell'elenco più piccolo $ [ {b, c }, {g, h }] $.

Questo tipo di problema è stato ben studiato? Esiste un algoritmo non approssimativo noto dato i vincoli aggiuntivi, che sarebbe migliore della programmazione dinamica ingenua? Un nome ben noto per la versione della cover set in cui non sono consentiti elementi extra sarebbero utili.