Simpler and faster algorithms for detours in planar digraphs
share
In the directed detour problem one is given a digraph G and a pair of vertices s and t, and the task is to decide whether there is a directed simple path from s to t in G whose length is larger than 𝖽𝗂𝗌𝗍_G(s,t). The more general parameterized variant, directed long detour, asks for a simple s-to-t path of length at least 𝖽𝗂𝗌𝗍_G(s,t)+k, for a given parameter k. 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 𝒪(n^3)-time algorithm for directed detour, while Fomin et al. [STACS 2022] gave a 2^𝒪(k)· n^𝒪(1)-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 𝒪(n^2) and directed long detour in time 2^𝒪(k)· n^4 log n. In both cases, the idea is to reduce to the 2-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.
READ FULL TEXT