Long Directed Detours: Reduction to 2-Disjoint Paths

2023/01/15 by Jacob, Ashwin, Włodarczyk, Michał, Zehavi, Meirav
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2301.06105

Abstract

We study an "above guarantee" version of the \sc Longest Path problem in directed graphs: We are given a graph G, two vertices s and t of G, and a non-negative integer k, and the objective is to determine whether G contains a path of length at least dist_G(s,t) +k where dist_G(s,t) is the length of a shortest path from s to t in G (assuming that one exists). We show that the problem is fixed parameter tractable (FPT) parameterized by k in the class of graphs where \sc 2-Disjoint Paths problem is polynomial time solvable.

Related

• Detours in Directed Graphs
• Faster Detours in Undirected Graphs
• A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
• Simpler and faster algorithms for detours in planar digraphs
• The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable