Fomin, Fedor V. ;
Golovach, Petr A. ;
Lochet, William ;
Sagunov, Danil ;
Simonov, Kirill ;
Saurabh, Saket
Detours in Directed Graphs
Abstract
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. [Ivona Bezáková et al., 2019] proved that on undirected graphs the problem is fixedparameter tractable (FPT) by providing an algorithm of running time 2^{O(k)}⋅ n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O (k)}· n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs.
In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k(diam(G)denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NPcomplete even for k=1. However, if the input undirected graph is 2connected, then the problem is FPT. On the other hand, for 2connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1,..., 4} and is NPcomplete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs.STACS.2022.29,
author = {Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Sagunov, Danil and Simonov, Kirill and Saurabh, Saket},
title = {{Detours in Directed Graphs}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {29:129:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15839},
URN = {urn:nbn:de:0030drops158390},
doi = {10.4230/LIPIcs.STACS.2022.29},
annote = {Keywords: longest path, longest detour, diameter, directed graphs, parameterized complexity}
}
09.03.2022
Keywords: 

longest path, longest detour, diameter, directed graphs, parameterized complexity 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 