Low-congestion shortcut and graph parameters
Tóm tắt
Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of
$${\tilde{\Omega }}(\sqrt{n} + D)$$
rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from special “hard-core” instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts was initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class
$${\mathcal {C}}$$
, an f-round algorithm for constructing shortcuts of quality q for any instance in
$${\mathcal {C}}$$
results in
$${\tilde{O}}(q + f)$$
-round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for
$${\mathcal {C}}$$
. The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking
$${\tilde{O}}(\sqrt{n}+D)$$
-round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known as short-hop extension, which might be of independent interest.
Tài liệu tham khảo
Abboud, A., Censor-Hillel, K., Khoury, S.: Near-linear lower bounds for distributed distance computations, even in sparse networks. In Proceedings of 30nd International Symposium on Distributed Computing (DISC), pp. 29–42 (2016). https://doi.org/10.1007/978-3-662-53426-7_3
Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In Proceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 364–369 (1989). https://doi.org/10.1109/SFCS.1989.63504
Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. (2005). https://doi.org/10.1137/S0097539701385351
Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial fpt algorithms for some classes of bounded clique-width graphs. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2765–2784 (2018). https://doi.org/10.1137/1.9781611975031.176
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. (2000). https://doi.org/10.1007/s002249910009
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. (2000). https://doi.org/10.1016/S0166-218X(99)00184-5
Damian, M., Pandit, S., Pemmaraju, S.: Distributed spanner construction in doubling metric spaces. In Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS), pp. 157–171 (2006). https://doi.org/10.1007/11945529_12
Elkin, M.: Distributed approximation: a survey. ACM SIGACT News (2004). https://doi.org/10.1145/1054916.1054931
Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. (2006). https://doi.org/10.1137/S0097539704441058
Elkin, M., Filtser, A., Neiman, O.: Distributed construction of light networks. arXiv (2019). arXiv:1905.02592
Gallager, R.G., Humblet, P.A., Spira, PM.: A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems (TOPLAS), pp. 66–77, 1983. https://doi.org/10.1145/357195.357200
Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. (1998). https://doi.org/10.1137/S0097539794261118
Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B (1974). https://doi.org/10.1016/0095-8956(74)90094-X
Ghaffari, M.: Near-optimal scheduling of distributed algorithms. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 3–12 (2015). https://doi.org/10.1145/2767386.2767417
Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202–219 (2016). https://doi.org/10.1137/1.9781611974331.ch16
Ghaffari, M., Kuhn, F.: Distributed MST and broadcast with fewer messages, and faster gossiping. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pp. 30:1–30:12 (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.30
Ghaffari, M., Kuhn, F., Su, H-H.: Distributed MST and routing in almost mixing time. In Proceedings of 31nd International Symposium on Distributed Computing (DISC), pp. 131–140 (2017). https://doi.org/10.1145/3087801.3087827
Ghaffari, M., Li, J.: New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pp. 31:1–31:16 (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.31
Gmyr, R., Pandurangan, G.: Time-message trade-offs in distributed algorithms. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pp. 32:1–32:18 (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.32
Haeupler, B., Hershkowitz, D.E., Wajc, D.: Round- and message-optimal distributed graph algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pp. 119–128 (2018). https://doi.org/10.1145/3212734.3212737
Haeupler, B., Izumi, T., Zuzic, G.: Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 451–460 (2016). https://doi.org/10.1145/2933057.2933112
Haeupler, B., Izumi, T., Zuzic, G.: Near-optimal low-congestion shortcuts on bounded parameter graphs. In Proceedings of 30nd International Symposium on Distributed Computing (DISC), pp. 158–172 (2016). https://doi.org/10.1007/978-3-662-53426-7_12
Haeupler, B., Li, J.: Faster distributed shortest path approximations via shortcuts. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pp. 33:1–33:14 (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.33
Haeupler, B., Li, J., Zuzic, G.: Minor excluded network families admit fast distributed algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pp. 465–474 (2018). https://doi.org/10.1145/3212734.3212776
Jurdzinski, T., Nowicki, K.: MST in O(1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2620–2632 (2018). https://doi.org/10.1137/1.9781611975031.167
Kitamura, N., Kitagawa, H., Otachi, Y., Izumi, T.: Low-congestion shortcut and graph parameters. In Proccedings of 33rd International Symposium on Distributed Computing (DISC), pp. 25:1–25:17, 2019. https://doi.org/10.4230/LIPIcs.DISC.2019.25
Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In Proccedings of 19th International Symposium on Distributed Computing (DISC), pp. 273–287 (2005). https://doi.org/10.1007/11561927_21
Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In Proceedings of the 24th annual ACM symposium on Principles of distributed computing (PODC), pp. 60–68 (2005). https://doi.org/10.1145/1073814.1073826
Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorith. (1998). https://doi.org/10.1006/jagm.1998.0929
Li, J.: Distributed treewidth computation. arXiv, 2018. arXiv:1805.10708
Li, J., Parter, M.: Planar diameter via metric compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 152–163 (2019). https://doi.org/10.1145/3313276.3316358
Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. Distrib. Comput. (2006). https://doi.org/10.1007/s00446-005-0127-6
Ookawa, H., Izumi, T.: Filling logarithmic gaps in distributed complexity for global problems. In Proccedings of 41st International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), pp. 377–388 (2015). https://doi.org/10.1007/978-3-662-46078-8_31
Pal, Madhumangal.: Intersection graphs: An introduction. arXiv, 2014. arXiv:1404.5468
Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 743–756 (2017). https://doi.org/10.1145/3055399.3055449
Pandurangan, G., Robinson, P., Scquizzato, M.: The distributed minimum spanning tree problem. Bulletin of the European Association for Theoretical Computer Science (EATCS) (2018). URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/538
Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. (2000). https://doi.org/10.1137/S0097539700369740
Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In Proceedings of the 43th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 363–372 (2011). https://doi.org/10.1145/1993636.1993686
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. (1981). https://doi.org/10.1016/0022-0000(81)90033-7