Simpler and faster algorithms for detours in planar digraphs
In the directed detour problem one is given a digraph and a pair of vertices and~, and the task is to decide whether there is a directed simple path from to in whose length is larger than . The more general parameterized variant, directed long detour, asks for a simple -to- path of length at least , for a given parameter . Surprisingly, it is still unknown whether directed detour is polynomial-time solvable on general digraphs. However, for planar digraphs, Wu and Wang~[Networks, '15] proposed an -time algorithm for directed detour, while Fomin et al.~[STACS 2022] gave a -time fpt algorithm for directed long detour. The algorithm of Wu and Wang relies on a nontrivial analysis of how short detours may look like in a plane embedding, while the algorithm of Fomin et al.~is based on a reduction to the -disjoint paths problem on planar digraphs. This latter problem is solvable in polynomial time using the algebraic machinery of Schrijver~[SIAM~J.~Comp.,~'94], but the degree of the obtained polynomial factor is huge. In this paper we propose two simple algorithms: we show how to solve, in planar digraphs, directed detour in time and directed long detour in time . In both cases, the idea is to reduce to the -disjoint paths problem in a planar digraph, and to observe that the obtained instances of this problem have a certain topological structure that makes them amenable to a direct greedy strategy.