グラフの直径(diameter)とは以下で定義される値 $D$ のことです:
D:=\max_{u,v\in V} \mathrm{dist}(u,v)
ここで $\mathrm{dist}(u,v)$ は二頂点 $u,v$ の最短経路長です. 最近の理論計算機科学の論文ではこの値の計算量に関する結果が散見されます. 本記事ではこれらの結果について, 備忘録がてらまとめます. 見逃しやミスがありましたらお知らせいただければ幸いです. 本記事で仮定する計算モデルは $O(\log n)$ bit word RAM モデルです.
まず, アルゴリズムに関しては以下のような結果が知られています.
ここで, $\tilde{O}(\cdot)$は polylog の factor を略しています.
| year | authors | time | comments |
|---|---|---|---|
| Folklore | $\tilde{O}(m+n)$ | Exact for trees; 2-approx. for graphs; | |
| Folklore | $\tilde{O}(mn^{1-\delta}/\epsilon)$ | $(1+\epsilon)$-approx for graphs of $D\geq n^{\delta}$; | |
| 1953 | Seidel [1] | $\tilde{O}(n^{\omega})$ | For undirected unweighted graphs; Computes APSP; |
| 1996 | Aingworth et al. [2,3] | $\tilde{O}(m\sqrt{n}+n^2)$ | For unweighted graphs; Approx. of $\lfloor 2/3D\rfloor\leq \mathrm{Algo} \leq D$; |
| 2006 | Boitmanis et al. [4] | $O(m\sqrt{n})$ | For undirected unweighted graphs; Additive $\sqrt{n}$-approx.; |
| 2013 | Weimann and Yuster [5,6] | $f(\epsilon)\cdot n(\log n)^4$ | For undirected planar graphs; $(1+\epsilon)$-approx.; |
| Roditty and V. Williams[7] | $O(m\sqrt{n})$ (expected) | Randomized; For unweighted graphs; Approx. of $\lfloor 2/3D\rfloor\leq \mathrm{Algo} \leq D$; | |
| $O(m^{2-\frac{1}{2h+3}})$ | For unweighted graphs; Approx. of $\lfloor 2/3D\rfloor\leq \mathrm{Algo} \leq D$, $h:=\lfloor D/3 \rfloor$; | ||
| 2014 | Chechik et al. [8] | $\tilde{O}(\min{m^{3/2},mn^{2/3}})$ | For weighted graphs; Approx. of $\lfloor 2/3D\rfloor\leq \mathrm{Algo} \leq D$; |
| 2016 | Damaschke [9] | $O(n+m\log n )$ | For graphs of $D\geq \delta n$ with $\delta>0.5$; |
| 2016 | Abboud et al. [10] | $2^{O(\mathrm{tw}\log \mathrm{tw})}\cdot n^{1+o(1)}$ | $\mathrm{tw}=\mathrm{treewidth}$; |
| Cairo et al. [11] | $O(mn^{\frac{1}{k+1}})$ (expected) | Randomized; $(2 − 1/2^k)$-approx for every k ≥ 0; | |
| Husfeldt [12] | $2^{O(\mathrm{tw}\log D)}\cdot n$ | ||
| 2017 | Cabello [13] | $\tilde{O}(n^{11/6})$ (expected) | Randomized; For planar graphs; |
| 2018 | Gawrychowski et al. [14] | $\tilde{O}(n^{5/3})$ | For planar graphs; |
| Coudert et al. [15] | $O(\mathrm{mw}^3+n+m)$ | $\mathrm{mw}=\mathrm{modular width}$. |
Hardnessについては次のような結果が知られています.
| year | authors | Refuting algorithm | comments |
|---|---|---|---|
| 2013 | Roditty and V. Williams [7] | $O(m^{2-\epsilon})$ time, $(1.5-\delta)$-approx. for $\forall\epsilon,\delta>0$. | For unweighted undirected; Under SETH; |
| 2016 | Abboud et al. [10] | $2^{o(\mathrm{tw})}\cdot n^{2-\epsilon}$ time, $(1.5-\delta)$-approx. for $\forall\epsilon,\delta>0$. | Under SETH; |
重み付きグラフの直径は全点対最短経路問題(APSP)を計算すれば求められ, APSPは$O(n^3)$時間で計算できます. しかし直径を$O(n^{2.999})$時間で計算するアルゴリズムはこれまで知られておらず, 出来ないのではないかと考える人もいます. APSPに関しては, APSP conjecture (APSPは$O(n^{2.999})$時間では計算できない) という予想が知られています.
そこで, 「直径が$O(n^{2.999})$時間で計算できるならばAPSPも然り」 ということを考えたくなる(つまり, APSP conjectureから直径の計算のhardnessを示したい)のですが、この主張の証明はHardness in Pにおける重要なOpen problemです.
Abboud et al. [16]は 直径の計算とReach Centralityの計算は subcubic equivalent (片方が$O(n^{2.999})$時間で解ければもう一方も然り) であること示しています. また, 同じ論文[16]はAPSPの計算とBetweenness contralityの計算がsubcubic equivalentであることを示しています.
少しinformalな表現が多いですが, ちゃんとしたstatementを知りたい方は fine-grained complexity, Hardness in P に関する文献を読んで見てください.
参考文献は以下:
| Ref | Authors | Title | Source |
|---|---|---|---|
| [1] | R. Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs | Journal of Computer and System Sciences, vol. 51, no. 3, pp. 400–403, 1995. |
| [2] | D. Aingworth, C. Chekuri, and R. Motuwani | Fast estimation of diameter and shortest paths (without matrix multiplication) | Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996. |
| [3] | D. Aingworth, C. Chekuri, P. Indyk, and R. Motuwani | Fast estimation of diameter and shortest paths (without matrix multiplication) | SIAM Journal on Computing, vol. 28, no. 4, pp. 1167–1181, 1999. |
| [4] | K. Boitmanis, K. Freivalds, P. Lediņš, and R. Opmanis | Fast and simple approximation of the diameter and radius of a graph | Proceedings of the 5th International Workshop on Experimental and Efficient Algorithms (WEA), 2006. |
| [5] | O. Weimann and R. Yuster | Approximating the diameter of planar graphs in near linear time | Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), 2013. |
| [6] | O. Weimann and R. Yuster | Approximating the diameter of planar graphs in near linear time | ACM Transactions on Algorithms, vol. 12, no. 1, pp. 1–13, 2016. |
| [7] | L. Roditty and V. V. Williams | Fast approximation algorithms for the diameter and radius of sparse graphs | Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 2013. |
| [8] | S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. V. Williams | Better approximation algorithms for the graph diameter | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. |
| [9] | P. Damaschke | Computing giant graph diameters | Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA), 2016. |
| [10] | A. Abboud, V. V. Williams, and J. Wang | Approximation and fixed parameter subquadratic algorithms for radius and diameter | Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. |
| [11] | M. Cairo, R. Grossi, and R. Rizzi | New bounds for approximating extremal distances in undirected graphs | Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. |
| [12] | T. Husfeldt | Computing graph distances parameterized by treewidth and diameter | Pro- ceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC), 2016. |
| [13] | S. Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs | Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017. |
| [14] | P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann | Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time | Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. |
| [15] | D. Coudert, G. Ducoffe, and A. Popa | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs | Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. |
| [16] | A. Abboud, F. Grandoni, and V. V. Williams | Subcubic equivalences between graph centrality problems, apsp and diameter | Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. |
こうして見ると, SODAの論文がめっちゃ多いですね.