论文标题
单源的定向k边缘连接性几乎紧密的近似硬度
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
论文作者
论文摘要
在$ k $连接的定向施材树问题（$ k $ -dst）中，我们获得了带有边缘成本的$ n $ vertex指示图$ g =（v，e）$，连接性要求$ k $，root $ r \ in v $和一组终端$ t \ subseteq v $。目标是找到一个最低成本子图$ h \ subseteq g $，该$ k $内部与root dertex $ r $ r $ to t $ in t $中的每个端子$ t \。 在本文中，我们显示了各种参数的$ K $ -DST的近似硬度，从而解决了一些长期存在的开放问题。 - $ω\ left（| t |/\ log | t | \ right）$ - 近似硬度，该硬度在标准假设$ \ mathrm {np} \ neq \ neq \ mathrm {zpp} $中。在坚固的种植集团假设下，无Xibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibiabibia的性比率[Manurangsi，Rubinstein and Schramm，ITCS 2021]。 后一个硬度结果与微不足道近似算法获得的$ | t | $的近似值相匹配，从而解决了长期的开放问题。 - $ω\ left（\ sqrt {2}^k / k \ right）$ - 在假设$ \ mathrm {np} \ neq \ neq \ mathrm {zpp} $下的$ k $ -dst的一般情况下的近似硬度。这是以可生存的网络设计问题而闻名的第一个硬度结果，其性比率为$ k $。 - $ω\ left（（（k/l）^{l/4} \ right）$ - $ k $ -dst的近似硬度，$ l $ layered graphs for $ l \ le \ le o \ left（\ log n \ right）$。这几乎与$ o（k^{l-1} \ cdot l \ cdot \ log | t |）$在$ o \ left（n^l \ right）$中获得的近似值与$ O（k^{l-1} \ cdot l \ cdot \ log | t |）$ - 由于laekhanukit [iCalp`16]。
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].
