Lower Bounds for Exact and Approximate k-Disjoint-Shortest-Paths

Add 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^{) time.}

• 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:

• Arts LR6
• Combinatorics and Probability seminar
• School of Mathematics events

Note that ex-directory lists are not shown.