In this paper we examine pursuit-evasion games
in which the pursuer has higher speed than the evader.
This scenario is motivated by visibility-based pursuit-evasion
problems, particularly by the question of what happens when
the pursuer loses visual track of the moving evader. In these
cases the pursuer has two options for recovering visual contact
with the evader: to perform search over the possible locations
where the evader might be moving, or to clear the environment,
in other words to progressively search it without allowing the
evader to move into locations that have already been cleared.
It has been shown that in sufficiently complex environments
a single pursuer having the same speed as the evader cannot
clear the environment. In this work we prove that computing
the minimum speed which enables a faster pursuer to clear a
graph environment is NP-hard. In light of this result we provide
an experimental comparison of randomized and deterministic
search strategies on planar graphs, which has practical significance
in search and rescue settings.