  We consider a class of pursuit-evasion problems where an evader enters a
directed acyclic graph and attempts to reach one of the terminal nodes. A
pursuer enters the graph at a later time and attempts to capture the evader
before it reaches a terminal node. The pursuer can only obtain information
about the evader's path via sensors located at each node in the graph; the
sensor measurements are either green or red (indicating whether or not the
evader has passed through that node). We first show that it is NP-hard to
determine whether the pursuer can enter with some nonzero delay and still be
guaranteed to capture the evader, even for the simplest case when the
underlying graph is a tree. This also implies that it is NP-hard to determine
the largest delay at which the pursuer can enter and still have a guaranteed
capture policy. We further show that it is NP-hard to approximate (within any
constant factor) the largest delay at which the pursuer can enter. Finally, we
provide an algorithm to compute the maximum pursuer delay for a class of
node-sweeping policies on tree networks and show that this algorithm runs in
linear-time for bounded-degree trees.
