Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

グラフの直径の計算量について

グラフの直径(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の論文がめっちゃ多いですね.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
3
Help us understand the problem. What are the problem?