Distributed 2-Vertex Connectivity Test of Graphs Using Local Knowledge

Authors: Brahim Hamid, Bertrand Le Saec, Mohamed Mosbah

Abstract:

The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a general and a constructive approach. The contribution of this paper is threefold. First, using a preconstructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph G, where M is the number of its edges, N the number of its nodes and Δ is its degree, our algorithms need the following requirements: The first one uses O(Δ×N2) steps and O(Δ×logΔ) bits per node. The second one uses O(Δ×N2) messages, O(N2) time and O(Δ × logΔ) bits per node. Furthermore, the studied network is semi-anonymous: Only the root of the pre-constructed spanning tree needs to be identified.

Keywords: Distributed computing, fault-tolerance, graph relabeling systems, local computations, local knowledge, message passing system, networks, vertex connectivity.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072624

References:

[1] M. Bahramgiri, M.T. Hajiaghayi, and V.S. Mirrokni. Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks. In In IEEE Int. Conf. on Computer Communications and Networks (ICCCN02), pages 392-397, 2002.
[2] A. H. Esfahanian and S.L. Hakimi. On computing the connectivities of graphs and digraphs. Networks, pages 355-366, 1984.
[3] S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4):507-518, 1975.
[4] H.N. Gabow. Using expander graphs to find vertex connectivity. In 41st Annual Symposium on Foundations of Computer Science, page 410, 2000.
[5] M. R. Henzinger, S. Rao, and H. N. Gabow. Computing vertex connectivity: new bounds from old techniques. J. Algorithms, 34(2):222- 250, 2000.
[6] I. Litovsky, Y. M'etivier, and E. Sopena. Graph relabeling systems and distributed algorithms. In World Scientific Publishing, editor, Handbook of graph grammars and computing by graph transformation, volume Vol. III, Eds. H. Ehrig, H.J. Kreowski, U. Montanari and G. Rozenberg, pages 1-56, 1999.
[7] Y. M'etivier, M. Mosbah, and A. Sellami. Proving distributed algorithms by graph relabeling systems: Example of tree in networks with processor identities. In applied Graph Transformations (AGT2002), Grenoble, April 2002.
[8] R. De Prisco, B. Lampson, and N. Lynch. Revisiting the paxos algorithm. In Lecture Notes in Computer Science: Distributed Algorithms, Proc. of 11th International Workshop, WDAG-97, Saarbr¨ucken, Germany, volume 1320, pages 111-125. Springer, sep 1997.
[9] R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1, pages 146-160, 1972.
[10] G. Tel. Introduction to distributed algorithms. Cambridge University Press, second edition, 2000.
[11] K. Wada and W. Chen. Optimal fault-tolerant routings with small routing tables for k-connected graphs. J. Discrete Algorithms, 2(4):517-530, 2004.
[12] D. West. Introduction to graph theory. Second edition. Prentice-Hall, 2nd ed. edition, 2001.