Доминантни скуп — разлика између измена

Аппрокимација проблема прекривача је такође проучена: фактор логаритамске апроксимације може се решити помоћу једноставног [[похлепни алгоритам|похлепог алгоритма]], и проналажење сублогаритамског приближног фактора је NP-тешко. Прецизније, похлепни алгоритам даје фактор 1 + log|''V''| апроксимације минимума доминантог скупа, и Раз и Сафра <ref>Raz & Safra</ref> (1997) показују да ниједан алгоритам не може достићи фактор апроксимације бољи од ''c’’ log|''V''| за неке ''c''> 0 осим ако је [[P]] = [[NP]].

 

 

Следећи пар редукција ( Кан 1992, стр 108-109) показује да су проблем минимума доминантног скупа и проблем скупа покривача еквивалентни у Л-редукцији: уколико дамо инстанцу једног проблема, можемо изградити еквивалентну инстанцу другог проблема.