2026-07-22T22:29:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20575 2024-08-23T05:50:28Z ddc:004 open_access

The Canadian Traveller Problem on Outerplanar Graphs Beaudou, Laurent Bergé, Pierre Chernyshev, Vsevolod Dailly, Antoine Gerard, Yan Lagoutte, Aurélie Limouzy, Vincent Pastor, Lucas Canadian Traveller Problem Online algorithms Competitive analysis Outerplanar graphs We study the k-Canadian Traveller Problem, where a weighted graph G = (V,E,ω) with a source s ∈ V and a target t ∈ V are given. This problem also has a hidden input E_* ⊊ E of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum distance. At the beginning of the walk, the blockages E_* are unknown: the traveller discovers that an edge is blocked when visiting one of its endpoints. Online algorithms, also called strategies, have been proposed for this problem and assessed with the competitive ratio, i.e., the ratio between the distance actually traversed by the traveller divided by the distance he would have traversed knowing the blockages in advance. Even though the optimal competitive ratio is 2k+1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs. This value 9 also stands as a lower bound for this family of graphs as we prove that, for any ε > 0, no strategy can achieve a competitive ratio 9-ε. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laurent Beaudou and Pierre Bergé and Vsevolod Chernyshev and Antoine Dailly and Yan Gerard and Aurélie Lagoutte and Vincent Limouzy and Lucas Pastor 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.19 urn:nbn:de:0030-drops-205750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode