2018-04-17

# Approximation and complexity of multi-target graph search and the Canadian traveler problem

## Publication

### Publication

*
Theoretical Computer Science
,
Volume 732
p. 14-
25
*

In the Canadian traveler problem, we are given an edge weighted graph with two specified vertices

*s*and*t*and a probability distribution over the edges that tells which edges are present. The goal is to minimize the expected length of a walk from*s*to*t*. However, we only get to know whether an edge is active the moment we visit one of its incident vertices. Under the assumption that the edges are active independently, we show NP-hardness on series-parallel graphs and give results on the adaptivity gap. We further show that this problem is NP-hard on disjoint-path graphs and cactus graphs when the distribution is given by a list of scenarios. We also consider a special case called the multi-target graph search problem. In this problem, we are given a probability distribution over subsets of vertices. The distribution specifies which set of vertices has targets. The goal is to minimize the expected length of the walk until finding a target. For the independent decision model, we show that the problem is NP-hard on trees and give a (3.59+ϵ)-approximation for trees and a (14.4+ϵ)-approximation for general metrics. For the scenario model, we show NP-hardness on star graphs.Additional Metadata | |
---|---|

, , , , | |

doi.org/10.1016/j.tcs.2018.04.022 | |

Theoretical Computer Science | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |

van Ee, M., & Sitters, R. (2018). Approximation and complexity of multi-target graph search and the Canadian traveler problem. Theoretical Computer Science, 732, 14–25. doi:10.1016/j.tcs.2018.04.022 |