Property testing of planarity in the CONGEST model
Tóm tắt
We give a distributed algorithm in the CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (Proceedings of the 30th International Symposium on Distributed Computing, pp. 43–56, 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph
$$G = (V,E)$$
and a distance parameter
$$\epsilon $$
, if G is planar, then every node outputs accept, and if G is
$$\epsilon $$
-far from being planar (i.e., more than
$$\epsilon \cdot |E|$$
edges need to be removed in order to make G planar), then with probability
$$1-1/\mathrm{poly}(n)$$
at least one node outputs reject. The algorithm runs in
$$O(\log |V|\cdot \mathrm{poly}(1/\epsilon ))$$
rounds, and we show that this result is tight in terms of the dependence on |V|. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs.
Tài liệu tham khảo
Akhoondian Amiri, S., Schmid, S., Siebertz, S.: A local constant factor MDS approximation for bounded genus graphs. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 227–233. ACM (2016)
Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput. 22(5–6), 363–379 (2010)
Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), pp. 393–402 (2008)
Boyer, J.M., Myrvoid, W.J.: On the cutting edge: simplified \(O(n)\) planrity by edge addition. J. Gr. Algorithms Appl. 8(3), 241–273 (2004)
Brakerski, Z., Patt-Shamir, B.: Distributed discovery of large near-cliques. Distrib. Comput. 24(2), 79–89 (2011)
Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), pp. 43–56 (2016)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32–53 (1986)
Czumaj, A., Goldreich, O., Ron, D., Seshadhri, C., Shapira, A., Sohler, C.: Finding cycles and trees in sublinear time. Random Struct. Algorithms 45(2), 139–184 (2014)
Czumaj, A., Monemizadeh, M., Onak, K., Sohler, C.: Planar graphs: random walks and bipartiteness testing. Random Struct. Algorithms 55(1), 104–124 (2019)
Czygrinow, A., Hańćkowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 78–92 (2008)
Eden, T., Levi, R., Ron, D.: Testing bounded arboricity. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 2081–2092 (2018)
Elkin, M., Neiman, O.: Efficient algorithms for constructing very sparse spanners and emulators. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), (pp. 652–669). Society for Industrial and Applied Mathematics (2017)
Even, G., Fischer, O., Fraigniaud, P., Gonen, T., Levi, R., Medina, M., Montealegre, P., Olivetti, D., Oshman, R., Rapaport, I., Todinca, I.: Three notes on distributed property testing. In: Proceedings of the 41st International Symposium on Distributed Computing (DISC), pp. 15:1–15:30 (2017)
Even, G., Levi, R., Medina, M.: Faster and simpler distributed algorithms for testing and correcting graph properties in the congest-model. CoRR, abs/1705.04898 (2017)
Even, S.: Graph Algorithms, 2nd edn. Cambridge University Press, Cambridge (2011)
Fichtenberger, H., Levi, R., Vasudev, Y., Wötzel, M.: A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic, pp. 52:1–52:14 (2018)
Fichtenberger, H., Vasudev, Y.: A two-sided error distributed property tester for conductance. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27–31, 2018, Liverpool, UK, pp. 19:1–19:15 (2018)
Fischer, O., Gershtein, S., Oshman, R.: On the multiparty communication complexity of testing triangle-freeness. In: Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC), pp. 111–120. ACM (2017)
Fischer, O., Gonen, T., Oshman, R.: Distributed property testing for subgraph-freeness revisited. CoRR, abs/1705.04033 (2017)
Fraigniaud, P., Montealegre, P., Olivetti, D., Rapaport, I., Todinca, I.: Distributed subgraph detection. CoRR, abs/1706.03996 (2017)
Fraigniaud, P., Olivetti, D.: Distributed detection of cycles. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 153–162. ACM (2017)
Fraigniaud, P., Rapaport, I., Salo, V., Todinca, I.: Distributed testing of excluded subgraphs. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), volume 9888 of LNCS, pp. 342–356. Springer (2016)
Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks I: Planar embedding. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 29–38 (2016)
Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and min-cut, pp. 202–219 (2016)
Ghaffari, M., Lymouri, C.: Simple and near-optimal distributed coloring for sparse graphs. In: Proceedings of the 41st International Symposium on Distributed Computing (DISC), pp. 18:1–18:16 (2017)
Ghaffari, M., Parter, M.: Near-optimal distributed DFS in planar graphs. In: Proceedings of the 41st International Symposium on Distributed Computing (DISC), pp. 21:1–21:16 (2017)
Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discrete Math. 1(4), 434 (1988)
Haeupler, B.: Private communication
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. ACM (2016)
Haeupler, B., Izumi, T., Zuzic, G.: Near-optimal low-congestion shortcuts on bounded parameter graphs. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), pp. 158–172. Springer (2016)
Haeupler, B., Li, J., Zuzic, G.: Minor excluded network families admit fast distributed algorithms. arXiv preprint arXiv:1801.06237 (2018)
Hassidim, A., Kelner, J. A., Nguyen, H. N., Onak, K.: Local graph partitions for approximation and testing. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 22–31 (2009)
Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)
Kumar, A., Seshadhri, C., Stolman, A.: Finding forbidden minors in sublinear time: A n\(\wedge \)1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 509–520 (2018)
Kumar, A., Seshadhri, C., Stolman, A.: Random walks and forbidden minors II: a poly(d\(\epsilon ^{-1}\))-query tester for minor-closed properties of bounded degree graphs. In: Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC), pp. 559–567 (2019)
Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. Theory of Graphs, International Syposium, Rome, July 1966 (1967)
Lenzen, C., Pignolet, Y.-A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119–137 (2013)
Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC), pp. 510–524 (2010)
Levi, R., Medina, M., Ron, D.: Property testing of planarity in the CONGEST model. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pp. 347–356 (2018)
Levi, R., Ron, D.: A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms 11(3), 24:1–24:13 (2015)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Peleg, D.: Distributed computing. SIAM Monographs on discrete mathematics and applications 5 (2000)
Yoshida, Y., Ito, H.: Testing outerplanarity of bounded degree graphs. Algorithmica 73(1), 1–20 (2015)