Abstrakt
Ukazujeme, že určit nejmenší počet četníků, kteří chytnou každého zloděje v daném grafu, je NP-těžké. Dále ukazujeme, že parametrizovaná verze tohoto problému je W[2]-těžká.
Ukazujeme, že určit nejmenší počet četníků, kteří chytnou každého zloděje v daném grafu, je NP-těžké. Dále ukazujeme, že parametrizovaná verze tohoto problému je W[2]-těžká.