Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.03933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909281128808448 |
|---|---|
| author | Chitnis, Rajesh Thomas, Samuel Wirth, Anthony |
| author_facet | Chitnis, Rajesh Thomas, Samuel Wirth, Anthony |
| contents | Given a graph $G=(V,E)$ and a set $T=\{ (s_i, t_i) : 1\leq i\leq k \}\subseteq V\times V$ of $k$ pairs, the $k$-vertex-disjoint-paths (resp. $k$-edge-disjoint-paths) problem asks to determine whether there exist~$k$ pairwise vertex-disjoint (resp. edge-disjoint) paths $P_1, P_2, ..., P_k$ in $G$ such that, for each $1\leq i\leq 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 each individual 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 Gap-ETH, there exists a constant $δ>0$ such that for any constant $0<ε\leq \frac{1}{2}$ and any computable function $f$, there is no $(\frac{1}{2}+ε)$-approx in $f(k)\cdot n^{δ\cdot k}$ time. We further strengthen our results as follows: Directed: Inapprox 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: Inapprox 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03933 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths Chitnis, Rajesh Thomas, Samuel Wirth, Anthony Data Structures and Algorithms Given a graph $G=(V,E)$ and a set $T=\{ (s_i, t_i) : 1\leq i\leq k \}\subseteq V\times V$ of $k$ pairs, the $k$-vertex-disjoint-paths (resp. $k$-edge-disjoint-paths) problem asks to determine whether there exist~$k$ pairwise vertex-disjoint (resp. edge-disjoint) paths $P_1, P_2, ..., P_k$ in $G$ such that, for each $1\leq i\leq 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 each individual 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 Gap-ETH, there exists a constant $δ>0$ such that for any constant $0<ε\leq \frac{1}{2}$ and any computable function $f$, there is no $(\frac{1}{2}+ε)$-approx in $f(k)\cdot n^{δ\cdot k}$ time. We further strengthen our results as follows: Directed: Inapprox 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: Inapprox 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$. |
| title | Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.03933 |