Complexity of Canadian traveler problem variants

DOI10.1016/J.TCS.2013.03.016MaRDI QIDQ386993zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 432827 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A note on the \(k\)-Canadian traveller problem
• Repeated-task Canadian traveler problem
• Shortest paths without a map
• Stochastic shortest path problems with recourse
• The Canadian Traveller Problem and its competitive analysis

Cited in

(8)

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