[Mittagsseminar TI] Mittagsseminar am Donnerstag, 19.09.

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

             Donnerstag, 19. September 2024, 12:00 Uhr, SR 046, 
Takustraße 9
            Sam Thomas (Birmingham & Melbourne)
            zum Thema:
Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Abstract:

Given a graph G and a set of $k$ terminal vertex pairs, the 
k-vertex-disjoint-paths (resp. k-edge-disjoint-paths) problem asks to 
determine whether there exists $k$ pairwise vertex-disjoint (resp. 
edge-disjoint) paths in G that connect the vertex pairs. 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 each path is further required 
to be a shortest path connecting its pair. They showed that the 
k-disjoint-shortest-paths problem is NP-complete on both directed and 
undirected graphs; this holds even if the graphs are planar and have 
unit edge lengths. We focus on four versions of the problem, 
corresponding to considering edge/vertex disjointness, and to 
considering directed/undirected graphs. Building on the reduction of 
Chitnis [SIDMA ’23] for k-edge-disjoint-paths on planar DAGs, we obtain 
the following inapproximability lower bound for each of the four 
versions of k-disjoint-shortest-paths on n-vertex graphs:

Under the gap version of the Exponential Time Hypothesis (Gap-ETH), 
there exists a constant δ > 0 such that for any constant 0 < ε ≤ 12 and 
any computable function f , there is no (1/2+ε)-approximation in f (k) · 
n^{δ·k} time.

We provide a single, unified framework to obtain lower bounds 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: The inapproximability lower bound for edge-disjoint (resp. 
vertex-disjoint) paths holds even if the input graph is a planar (resp. 
1-planar) DAG with max in-degree and max out-degree at most 2.

Undirected: The inapproximability lower bound for edge-disjoint (resp. 
vertex-disjoint) paths hold even if the input graph is planar (resp. 
1-planar) and has max degree 4.
The reductions outlined in this paper produce graphs in which half of 
the terminal pairs are trivially satisfiable, so any improvement of our 
( 1/2 +ε) inapproximability factor requires a different approach.
As a byproduct of our reductions, we also show that the exact version of 
each problem is W[1]-hard and give a f (k) · n^{o(k)}-time lower bound 
for them under ETH. This exact lower bound shows that the n^{O(k)}-time 
algorithms of Berczi and Kobayashi [ESA ‘17] for Directed-k-EDSP and 
Directed-k-VDSP are tight.

Full paper at https://arxiv.org/abs/2408.03933

Bio:

Sam has been a Priestly PhD scholar at the Universities of Birmingham 
and Melbourne since February 2022 under the supervision of Rajesh 
Chitnis and Tony Wirth. He is working under the title of “Obtaining Time 
& Space Lower Bounds for Parameterised Algorithms” and has been based in 
Sydney since April 2024. His research has predominantly focused on 
parameterised complexity, with a particular focus on disjoint paths 
algorithms. Prior to beginning his PhD, Sam completed an MSci with 
Honours in Computer Science from the University of Birmingham and spent 
time working as a C++ software engineer.

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature