Abstract
The kDetour problem is a basic pathfinding problem: given a graph G on n vertices, with specified nodes s and t, and a positive integer k, the goal is to determine if G has an stpath of length exactly dist(s,t) + k, where dist(s,t) is the length of a shortest path from s to t. The kDetour problem is NPhard when k is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in f(k)poly(n) time, for f(⋅) as slowgrowing as possible.
We present faster algorithms for kDetour in undirected graphs, running in 1.853^k poly(n) randomized and 4.082^kpoly(n) deterministic time. The previous fastest algorithms for this problem took 2.746^k poly(n) randomized and 6.523^k poly(n) deterministic time [BezákováCurticapeanDellFomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length k in undirected graphs [BjörklundHusfeldtKaskiKoivisto, JCSS 2017], intuitively by looking for paths of length k in randomly bipartitioned subgraphs. Our algorithms for kDetour stem from a new application of this idea, which does not involve choosing the bipartitioned subgraphs randomly.
Our work has direct implications for the kLongest Detour problem, another related pathfinding problem. In this problem, we are given the same input as in kDetour, but are now tasked with determining if G has an stpath of length at least dist(s,t)+k. Our results for kDetour imply that we can solve kLongest Detour in 3.432^k poly(n) randomized and 16.661^k poly(n) deterministic time. The previous fastest algorithms for this problem took 7.539^k poly(n) randomized and 42.549^k poly(n) deterministic time [Fomin et al., STACS 2022].
BibTeX  Entry
@InProceedings{akmal_et_al:LIPIcs.ESA.2023.7,
author = {Akmal, Shyan and Vassilevska Williams, Virginia and Williams, Ryan and Xu, Zixuan},
title = {{Faster Detours in Undirected Graphs}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {7:17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18660},
URN = {urn:nbn:de:0030drops186601},
doi = {10.4230/LIPIcs.ESA.2023.7},
annote = {Keywords: path finding, detours, parameterized complexity, exact algorithms}
}
Keywords: 

path finding, detours, parameterized complexity, exact algorithms 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 