论文标题
有条件的最佳近似算法是有向图的周长
Conditionally optimal approximation algorithms for the girth of a directed graph
论文作者
论文摘要
众所周知，在密集的未加权图中，围绕围栏的$ 2 $ Approximation算法需要$ n^{3-o（1）} $时间，除非有人使用快速矩阵乘法。同时，在$ O（Mn^{1-ε}）$ TIME（Chechik等人）中运行的组合算法的最著名近似因素是$ 3 $。真正的答案是$ 2 $还是$ 3 $？ 本文的主要结果是（有条件的）紧密近似算法的有向图。首先，我们表明，在一个流行的硬度假设下，任何算法，即使是利用快速矩阵乘法的算法，也需要至少在某些稀疏$ m $中占用至少$ mn^{1-o（1）} $时间，如果它获得了$（2--ε）$ - 对于任何$ε> 0 $。第二，我们给出了$ 2 $ - APPRXIMATION算法，用于以$ \ tilde {o}（Mn^{3/4}）$ time运行的未加权图，以及$（2+ε）$ - 近似算法（对于任何$ε> 0 $）（对于$ε> 0 $）（用于$ε> 0美元） n）$时间。我们的算法是组合。 我们还获得了$（4+ε）$ - 在$ \ tilde {o}（Mn^{\ sqrt {2} -1}）$时间中运行的围绕腰围的近似，从而改善了以前的最佳$ \ tilde {o}（M \ sqrt n）$运行时间。最后，我们考虑往返跨度的计算。我们在$ \ tilde {o}（n^{1.5}/ε^2）$ \ tilde {o}（m \ sqrt n/ε^2）$（m \ tilde {o}中获得$（5+ε）$ - 近似圆形扳手。这对Chechik等人的先前近似因子$（8+ε）$进行了改善。在相同的运行时间。
It is known that a better than $2$-approximation algorithm for the girth in dense directed unweighted graphs needs $n^{3-o(1)}$ time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in $O(mn^{1-ε})$ time (by Chechik et al.) is $3$. Is the true answer $2$ or $3$? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least $mn^{1-o(1)}$ time for some sparsity $m$ if it achieves a $(2-ε)$-approximation for any $ε>0$. Second we give a $2$-approximation algorithm for the girth of unweighted graphs running in $\tilde{O}(mn^{3/4})$ time, and a $(2+ε)$-approximation algorithm (for any $ε>0$) that works in weighted graphs and runs in $\tilde{O}(m\sqrt n)$ time. Our algorithms are combinatorial. We also obtain a $(4+ε)$-approximation of the girth running in $\tilde{O}(mn^{\sqrt{2}-1})$ time, improving upon the previous best $\tilde{O}(m\sqrt n)$ running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a $(5+ε)$-approximate roundtrip spanner on $\tilde{O}(n^{1.5}/ε^2)$ edges in $\tilde{O}(m\sqrt n/ε^2)$ time. This improves upon the previous approximation factor $(8+ε)$ of Chechik et al. for the same running time.
