A Study On Low Complexity Distributed K-connectivity Testing Algorithm

In recent years,with the increase of graph scale and graph data volume,the research of distributed graph computing problem has attracted more and more attention.In the design of distributed graph algorithms,the CONGEST model is one of the most widely used research models.However,the limitation of bandwidth usually makes some complex graph computing problems unsatisfactory in terms of time complexity(Round complexity is usually used to measure the time complexity of distributed algorithm).The distributed graph property testing is an effective method to reduce the round complexity of algorithm.According to whether a given graph satisfies the target property or isε-far from satisfying the target property,the graph property testing algorithm will output a positive or negative result with a certain probability(generally 2/3).To highlight the improvement of the graph property testing algorithm for distributed graph computing in terms of time efficiency,the k-edge(vertex)connectivity testing can be an entry point to discuss how to efficiently design a distributed k-edge(vertex)connectivity testing algorithm that meets the CONGEST model.If there are k-edge(vertex)-disjointed paths between any two vertices of a given graph,then the graph is said to be k-edge(vertex)connected.Connectivity is a global property of the graph,and exact computation of this property requires global communication,which makes the round complexity of the algorithm heavily dependent on the graph size.To solve this problem,a distributed k-edge(vertex)connectivity testing algorithm is first proposed under the CONGEST model,which can be applied to both undirected and directed graphs.The newly proposed distributed testing algorithm uses the equivalence principle of edge connectivity and the edge augmentation technology of vertex connectivity to divide the entire graph into a large number of small components.By processing these small components,the testing algorithm can not only ease the pressure on the bandwidth of communication between vertices,but also get rid of the dependence of the time complexity on the scale of the graph.In addition,the new algorithm expands the research model of the sequential connectivity testing algorithm from the bounded-degree graph model to the sparse graph model,which improves the scope of application of the algorithm.With the help of these technical methods,the round complexity of the new algorithm no longer depends on the scale of the graph and the round complexity is O(c~k/ε~k),wherec,k andεare all constant parameters.The experimental simulation further verifies the improvement in the round complexity brought by the new algorithm.