  In network interdiction problems, evaders (e.g., hostile agents or data
packets) may be moving through a network towards targets and we wish to choose
locations for sensors in order to intercept the evaders before they reach their
destinations. The evaders might follow deterministic routes or Markov chains,
or they may be reactive}, i.e., able to change their routes in order to avoid
sensors placed to detect them. The challenge in such problems is to choose
sensor locations economically, balancing security gains with costs, including
the inconvenience sensors inflict upon innocent travelers. We study the
objectives of 1) maximizing the number of evaders captured when limited by a
budget on sensing cost and 2) capturing all evaders as cheaply as possible. We
give optimal sensor placement algorithms for several classes of special graphs
and hardness and approximation results for general graphs, including for
deterministic or Markov chain-based and reactive or oblivious evaders. In a
similar-sounding but fundamentally different problem setting posed by
Rubinstein and Glazer where both evaders and innocent travelers are reactive,
we again give optimal algorithms for special cases and hardness and
approximation results on general graphs.
