2016/09/13 by Shreyas Sundaram, Sundaram, Shreyas, Krishnamoorthy Kalyanam +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1609.03664
arxiv created 2016/09/13 · arxiv updated 2016/09/14
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.