Complexity of Canadian traveler problem variants

DOI10.1016/J.TCS.2013.03.016zbMATH Open1277.68087DBLPjournals/tcs/FriedSBW13arXiv1207.4710OpenAlexW2009831508WikidataQ57518721 ScholiaQ57518721MaRDI QIDQ386993FDOQ386993

Authors: Dror Fried, Solomon E. Shimony, Amit Benbassat, Cenny Wenner 

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The Canadian traveler problem (CTP) is the problem of traversing a given graph, where some of the edges may be blocked - a state which is revealed only upon reaching an incident vertex. Originally stated by Papadimitriou and Yannakakis (1991), the adversarial version of CTP was shown to be PSPACE-complete, with the stochastic version shown to be #P-hard. We show that stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of stochastic CTP,and proceeding with gadgets that allow us to extend the proof to the independent case. Since for disjoint-path graphs, CTP can be solved in polynomial time, we examine the complexity of the more general remote-sensing CTP, and show that it is NP-hard even for disjoint-path graphs.

Full work available at URL: https://arxiv.org/abs/1207.4710

Recommendations

• Canadians should travel randomly
• Generalized Canadian traveller problems
• An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• Repeated-task Canadian traveler problem

zbMATH Keywords

Canadian traveler problemcomplexity of navigation under uncertaintystochastic shortest path with recourse

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Stochastic shortest path problems with recourse
• Shortest paths without a map
• Title not available (Why is that?)
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• Repeated-task Canadian traveler problem

Cited In (8)

• Canadian traveller problem with predictions
• Repeated-task Canadian traveler problem
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• Approximating the Canadian traveller problem with online randomization
• The Canadian Traveller Problem and its competitive analysis
• An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem
• Multiple canadians on the road: minimizing the distance competitive ratio
• The covering Canadian traveller problem

This page was built for publication: Complexity of Canadian traveler problem variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386993)