Simpler and faster algorithms for detours in planar digraphs

DOI10.1137/1.9781611977585.CH15MaRDI QIDQ6422726zbMATH OpenOpenAlexFDO

Authors Meike Hatzel, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski

Publication date 6 January 2023

Full work available at URL https://doi.org/10.1137/1.9781611977585.ch15

Abstract: 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

m a t h s f {d i s t}_{G} (s, t)

. The more general parameterized variant, directed long detour, asks for a simple

s

-to-

t

path of length at least

m a t h s f {d i s t}_{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

m a t h c a l O (n^{3})

-time algorithm for directed detour, while Fomin et al.~[STACS 2022] gave a

2^{m a t h c a l O (k)} c d o t n^{m a t h c a l O (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

S

-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

m a t h c a l O (n^{2})

and directed long detour in time

2^{m a t h c a l O (k)} c d o t n^{4} l o g 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.

Cited in

(2)

This page was built for publication: Simpler and faster algorithms for detours in planar digraphs

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