Abstract
We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing \(\mathcal {CONGEST}_\mathrm{BC}\) model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms.
Similar content being viewed by others
Notes
that is half of a positive integer, like 5 / 2.
References
Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput. 22, 363–379 (2010)
Barenboim, L., Elkin, M., Kuhn, F.: Distributed \((\Delta +1)\)-coloring in linear (in \(\Delta \)) time. SIAM J. Comput. 43, 72–95 (2014)
Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., Müller, H., Tuza, Z. (1995) Rankings of graphs. In: Graph-Theoretic Concepts in Computer Science (Lecture notes in computer science), vol. 903/1995. Springer, pp. 292–304
Deogun, J., Kloks, T., Kratsch, D., Müller, H. (1994) On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E., Wagner, K. (eds.), Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science (Lecture notes in computer science), vol. 775. Springer, pp. 747–758
Dvořák, Z.: Asymptotical structure of combinatorial objects, PhD thesis, Charles University, Faculty of Mathematics and Physics (2007)
Dvořák, Z.: Constant-factor approximation of domination number in sparse graphs. Eur. J. Combin. 34, 833–840 (2013)
Dvořák, Z., Kráľ, D.: Algorithms for classes of graphs with bounded expansion, Lecture Notes in Computer Science, 5911 LNCS, pp. 17–32 (2010)
Dvořák, Z., Kráľ, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 133–142. (2010)
Dvořák, Z., Kráľ, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs, J. ACM, 60:5 Article 36 (2013)
Dvořák, Z., Kupec, M., Tůma, V.: Dynamic data structure for tree-depth decomposition. arXiv:1307.2863 [cs.DS]. July 2013
Gajarský, J., Hliněný, P., Obdržálek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Sánchez Villamil, F., Sikdar, S.: Kernelization using structural parameters on sparse graph classes In: ESA 2013. Lecture Notes in Computer Science, vol. 8125, pp. 529–540. Springer, Heidelberg (2013)
Goldberg, A.V., Plotkin, S.A.: Parallel \((\Delta +1)\)-coloring of constant-degree graphs. Inf. Process. Lett. 25, 241–245 (1987)
Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, pp. 181–206. (2011)
Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, New York, NY, USA, 2014, ACM, pp. 89–98 (2014)
Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Publishers Inc, San Francisc, USA (2013)
Kazana, W., Segoufin, L.: Enumeration of first-order queries on classes of structures with bounded expansion. In: Proceedings of the 16th International Conference on Database Theory, pp. 10–20 (2013)
Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 7–15 (2006)
Lenzen, C., Wattenhofer, R. (2010) Minimum dominating set approximation in graphs of bounded arboricity. In: Lynch, N., Shvartsman, A. (eds.) Distributed Computing (Lecture notes in computer science) vol. 6343. Springer, Berlin Heidelberg, pp. 510–524
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21, 193–201 (1992)
Nešetřil, J., Ossona de Mendez, P. (2005) The grad of a graph and classes with bounded expansion. In: Raspaud, A., Delmas, O. (eds.), 7th International Colloquium on Graph Theory (Electronic notes in discrete mathematics), vol. 22. Elsevier, pp. 101–106
Nešetřil, J., Ossona de Mendez, P. (2006) Linear time low tree-width partitions and algorithmic consequences. In: STOC’06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM Press, pp. 391–400
Nešetřil, J., Ossona de Mendez, P.: Tree depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27, 1022–1041 (2006)
Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. decompositions. Eur. J. Comb. 29, 760–776 (2008)
Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. algorithmic aspects. Eur. J. Comb. 29, 777–791 (2008)
Nešetřil, J.: Ossona de Mendez, P.: How many F’s are there in G? Eur. J. Comb. 32, 1126–1141 (2011)
Nešetřil, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms), vol. 28 of Algorithms and Combinatorics. Springer, Berlin (2012)
Nešetřil, J., Ossona de Mendez, P. (2015) On first-order definable colorings. In: Nešetřil, J., Pellegrini, M. (eds.), Geometry, Structure and Randomness in Combinatorics, vol. 18 of Publications of the Scuola Normale Superiore, CRM Series, Edizioni della Normale, pp. 99–122
Nešetřil, J., Ossona de Mendez, P.: On low tree-depth decompositions. Graphs Comb. 31, 1–23 (2015)
Nešetřil, J., Ossona de Mendez, P., Wood, D.: Characterizations and examples of graph classes with bounded expansion. Eur. J. Comb. 33, 350–373 (2012)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Schäffer, A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33, 91–96 (1989/90)
Szegedy, M., Vishwanathan, S. (1993) Locality based graph coloring. In: Proceedings 25th ACM Symposium on Theory of Computing, pp. 201–207
Yang, D.: Generalization of transitive fraternal augmentations for directed graphs and its applications. Discrete Math. 309, 4614–4623 (2009)
Zhu, X.: Colouring graphs with bounded generalized colouring number. Discrete Math. 309, 5562–5568 (2009)
Acknowledgments
The authors would like to thank the referees for their many remarks, which allowed to improve the quality of the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by grant ERCCZ LL-1201 of the Czech Ministry of Education and LEA STRUCO.
J. Nešetřil: Supported by grant CE-ITI P202/12/G061 of GAČR.
P. Ossona de Mendez: Supported by ANR STINT.
Rights and permissions
About this article
Cite this article
Nešetřil, J., de Mendez, P.O. A distributed low tree-depth decomposition algorithm for bounded expansion classes. Distrib. Comput. 29, 39–49 (2016). https://doi.org/10.1007/s00446-015-0251-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-015-0251-x