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

Martijn van Ee*, René Sitters

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

19 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)14-25
Number of pages12
JournalTheoretical Computer Science
Volume732
Early online date17 Apr 2018
DOIs
Publication statusPublished - 7 Jul 2018

Keywords

  • Approximation algorithms
  • Canadian traveler problem
  • Computational complexity
  • Graph search problem
  • Routing under uncertainty

Fingerprint

Dive into the research topics of 'Approximation and complexity of multi-target graph search and the Canadian traveler problem'. Together they form a unique fingerprint.

Cite this