Computer Science Seminar
Date: Wednesday, 6 March 2024
Time: 3:30 PM
Venue: Lecture Hall 5
Using a Geometric Lens to find k Disjoint Shortest Paths
Matthias Bentert
University of Bergen.
06-03-24

---

Abstract

Given an undirected graph and k pairs of terminal vertices (s_i, t_i), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_i where P_i is a shortest s_i-t_i-path. Recently, Lochet [SODA ’21] provided an algorithm that solves k-DSP in n O(k^5^k) time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(n^(16k·k!))-time algorithm based on a novel geometric view on this problem. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.

This is joint work with André Nichterlein, Malte Renken, and Philipp Zschoche.