---
title: "Algorithms and Complexity Results for Pursuit-Evasion Problems"
authors:
  - "Richard B. Borie"
  - "Craig A. Tovey"
  - "Sven Koenig"
doi: ""
url: "https://ijcai.org/proceedings/2009/21"
pdf: "https://ijcai.org/proceedings/2009/0021.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "59-65"
track: ""
keywords:
---

# Algorithms and Complexity Results for Pursuit-Evasion Problems

Richard B. Borie, Craig A. Tovey, Sven Koenig

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 59-65.

## Abstract

We study pursuit-evasion problems where a number of pursuers have to clear a given graph. We study when polynomial-time algorithms exist to determine how many pursuers are needed to clear a given graph and how a given number of pursuers should move on the graph to clear it with either a minimum sum of their travel distances or minimum task-completion time. We generalize prior work to both unit-width arbitrary-length and unit-length arbitrary-width graphs and derive both algorithms and complexity results for a variety of graph topologies. In this context, we describe a polynomial-time algorithm, called CLEARTHETREE, that is much shorter and algorithmically simpler than the state-of-the-art algorithm for the minimum pursuer problem on trees. Our theoretical research lays a firm theoretical foundation for pursuit evasion on graphs and informs practitioners about which problems are easy and which ones are hard.Richard Borie, Craig Tovey, Sven Koenig