Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916362115350528 |
|---|---|
| author | Liao, Chao Chen, Qingyun Laekhanukit, Bundit Zhang, Yuhao |
| author_facet | Liao, Chao Chen, Qingyun Laekhanukit, Bundit Zhang, Yuhao |
| contents | In the $k$-connected directed Steiner tree problem ($k$-DST), we are given an $n$-vertex directed graph $G=(V,E)$ with edge costs, a connectivity requirement $k$, a root $r\in V$ and a set of terminals $T\subseteq V$. The goal is to find a minimum-cost subgraph $H\subseteq G$ that has $k$ internally disjoint paths from the root vertex $r$ to every terminal $t\in T$.
In this paper, we show the approximation hardness of $k$-DST for various parameters, which thus close some long-standing open problems.
- $Ω\left(|T|/\log |T|\right)$-approximation hardness, which holds under the standard assumption $\mathrm{NP}\neq \mathrm{ZPP}$. The inapproximability ratio is tightened to $Ω\left(|T|\right)$ under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021].
The latter hardness result matches the approximation ratio of $|T|$ obtained by a trivial approximation algorithm, thus closing the long-standing open problem.
- $Ω\left(\sqrt{2}^k / k\right)$-approximation hardness for the general case of $k$-DST under the assumption $\mathrm{NP}\neq\mathrm{ZPP}$. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in $k$.
- $Ω\left((k/L)^{L/4}\right)$-approximation hardness for $k$-DST on $L$-layered graphs for $L\le O\left(\log n\right)$. This almost matches the approximation ratio of $O(k^{L-1}\cdot L \cdot \log |T|)$ achieving in $O\left(n^L\right)$-time due to Laekhanukit [ICALP`16]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_13088 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity Liao, Chao Chen, Qingyun Laekhanukit, Bundit Zhang, Yuhao Data Structures and Algorithms Computational Complexity Optimization and Control 68Q17 F.2.2; G.2.2 In the $k$-connected directed Steiner tree problem ($k$-DST), we are given an $n$-vertex directed graph $G=(V,E)$ with edge costs, a connectivity requirement $k$, a root $r\in V$ and a set of terminals $T\subseteq V$. The goal is to find a minimum-cost subgraph $H\subseteq G$ that has $k$ internally disjoint paths from the root vertex $r$ to every terminal $t\in T$. In this paper, we show the approximation hardness of $k$-DST for various parameters, which thus close some long-standing open problems. - $Ω\left(|T|/\log |T|\right)$-approximation hardness, which holds under the standard assumption $\mathrm{NP}\neq \mathrm{ZPP}$. The inapproximability ratio is tightened to $Ω\left(|T|\right)$ under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of $|T|$ obtained by a trivial approximation algorithm, thus closing the long-standing open problem. - $Ω\left(\sqrt{2}^k / k\right)$-approximation hardness for the general case of $k$-DST under the assumption $\mathrm{NP}\neq\mathrm{ZPP}$. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in $k$. - $Ω\left((k/L)^{L/4}\right)$-approximation hardness for $k$-DST on $L$-layered graphs for $L\le O\left(\log n\right)$. This almost matches the approximation ratio of $O(k^{L-1}\cdot L \cdot \log |T|)$ achieving in $O\left(n^L\right)$-time due to Laekhanukit [ICALP`16]. |
| title | Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity |
| topic | Data Structures and Algorithms Computational Complexity Optimization and Control 68Q17 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2202.13088 |