TY - JOUR

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

AU - van Ee, Martijn

AU - Sitters, René

PY - 2018/7/7

Y1 - 2018/7/7

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Canadian traveler problem

KW - Computational complexity

KW - Graph search problem

KW - Routing under uncertainty

UR - http://www.scopus.com/inward/record.url?scp=85045924624&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045924624&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.04.022

DO - 10.1016/j.tcs.2018.04.022

M3 - Article

AN - SCOPUS:85045924624

SN - 0304-3975

VL - 732

SP - 14

EP - 25

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -