Abstrakt
Dokazujeme, že určit minimální počet policistů potřebných k dopadení zloděje v daném grafu je NP-těžký problém a že parametrizovaná verze tohoto problému je W[2]-těžká. V případě zloděje, který je s-krát rychlejší než policisté, je pro split grafy úloha polynomiální pro s=1 a NP-těžká pro s=2.
Pro rovinné grafy ukazujeme, že v případě s>1 je minimální počet policistů potřebných k dopadení zloděje neomezený.