University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Lower Bounds for Exact and Approximate k-Disjoint-Shortest-Paths

## Lower Bounds for Exact and Approximate k-Disjoint-Shortest-PathsAdd to your list(s) Download to your calendar using vCal - Sam Thomas (Birmingham/Melbourne)
- Thursday 20 April 2023, 15:00-16:00
- Arts LR6.
If you have a question about this talk, please contact Dr Richard Mycroft. Given a graph G and a set T = {(s_i, t_i) : 1 ≤ i ≤ k} of k pairs, the k-Vertex-Disjoint-Paths (resp. k-Edge-Disjoint-Paths) problem asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P_1, P_2, ... , P_k in G such that, for each 1 ≤ i ≤ k, P_i connects s_i to t_i. Both the edge-disjoint and vertex-disjoint versions in undirected graphs are famously known to be FPT (parameterized by k) due to the Graph Minor Theory of Robertson and Seymour. Eilam-Tzoreff [DAM ’98] introduced a variant, known as the k-Disjoint-Shortest-Paths problem, where the individual paths are further required to be shortest paths connecting each pair. They showed that the k-Disjoint-Shortest-Paths problem is NP-complete on both directed and undirected graphs, even when they are planar and have unit edge lengths. There are four versions of the k-Disjoint-Shortest-Paths problem, depending on whether we require edge-disjointness or vertex-disjointness and if the input graph is directed or undirected. Building on the reduction of Chitnis [CIAC ’21] for k-Edge-Disjoint-Paths on planar DAGs, we obtain the following two types of lower bounds for each of the aforementioned four versions of k-Disjoint-Shortest-Paths on graphs with n vertices: • Exact lower bound: Under the Exponential Time Hypothesis (ETH), there is no computable function f such that there is an exact algorithm running in f(k) n • Approximation lower bound: Under the gap version of the Exact Exponential Hypothesis (Gap-ETH), there exist constants ϵ, δ > 0 such that for any computable function f there is no (1/2+ϵ)-approximation in f(k) n(δk) time. For each of the four versions of k-Disjoint-Shortest-Paths, we are able to further strengthen our results by restricting the structure of the input graphs in the lower bound constructions as follows: • Directed edge-disjoint: The two lower bounds hold even if the input graph is a planar DAG with max in-degree and max out-degree at most 2. • Directed vertex-disjoint: The two lower bounds hold even if the input graph is a 1-planar DAG with max in-degree and max out-degree at most 2. • Undirected edge-disjoint: The two lower bounds hold even if the input graph is planar and has max degree 4. • Undirected vertex-disjoint: The two lower bounds hold even if the input graph is 1-planar and has max degree 4. We understand these are the first FPT (in)approximability results for any variant of the k-Disjoint-Paths problem, on directed or undirected graphs. Our exact lower bounds show that the n^(O(k))-time algorithms of Berczi and Kobayashi [ESA ’17] for the vertex-disjoint version on planar directed graphs and edge-disjoint version on undirected planar graphs are asymptotically optimal. The inapproximability results are tight for our specific reductions because in all our instances of Disjoint-Shortest-Paths it is trivially possible to satisfy half the pairs. This talk is part of the Combinatorics and Probability seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsJane Langdale Applied Topology Colloquium School of Mathematics events## Other talksTBA The Electron-Ion Collider Integral equation methods for acoustic scattering by fractals Kneser Graphs are Hamiltonian The tragic destiny of Mileva Marić Einstein Parameter estimation for macroscopic pedestrian dynamics models using trajectory data |