Exact Exponential Algorithms

In the Terrain Guarding problem, the input is a terrain and a positive integer k, and the task is to decide whether one can place guards on at most k points on a given terrain such

In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem