William Lochet. A polynomial time algorithm for the k-disjoint shortest path problem скачать в хорошем качестве

William Lochet. A polynomial time algorithm for the k-disjoint shortest path problem

Talks on Frontiers of Parameterized Complexity https://frontpc.blogspot.com Keywords: disjoint shortest paths October 15, 2020 William Lochet, University of Bergen Title: A polynomial time algorithm for the k-disjoint shortest path problem Abstract: The disjoint paths problem is a fundamental problem in algorithmic graph theory. For a given graph G and a set of k pairs of terminals in G, it asks for the existence of k vertex-disjoint paths connecting each pair of terminals. Very famously, Robertson and Seymour proved the existence of a n^3 algorithm for any fixed k in 1995 as part of the Graph Minor project. In this talk, we focus on the version of this problem where all the paths are required to be shortest paths. This was first introduced as the disjoint shortest paths problem by Eilam-Tzoreff in 1998 where she proved that the case k = 2 admits a polynomial time algorithm. She also asked for the existence of a polynomial time algorithm for any fixed k, a question which remained open even for the case k = 3. The goal of this talk is to prove that, for any fixed k, there exists a n^{f(k)} algorithm for the k-disjoint shortest paths problem, answering Eilam-Tzoreff's question.