Distributed Testing of Graph Isomorphism in the CONGEST model
share
In this paper we study the problem of testing graph isomorphism (GI) in the CONGEST distributed model. In this setting we test whether the distributive network, G_U, is isomorphic to G_K which is given as an input to all the nodes in the network, or alternatively, only to a single node. We first consider the decision variant of the problem in which the algorithm distinguishes G_U and G_K which are isomorphic from G_U and G_K which are not isomorphic. We provide a randomized algorithm with O(n) rounds for the setting in which G_K is given only to a single node. We prove that for this setting the number of rounds of any deterministic algorithm is Ω̃(n^2) rounds, where n denotes the number of nodes, which implies a separation between the randomized and the deterministic complexities of deciding GI. We then consider the property testing variant of the problem, where the algorithm is only required to distinguish the case that G_U and G_K are isomorphic from the case that G_U and G_K are far from being isomorphic (according to some predetermined distance measure). We show that every algorithm requires Ω(D) rounds, where D denotes the diameter of the network. This lower bound holds even if all the nodes are given G_K as an input, and even if the message size is unbounded. We provide a randomized algorithm with an almost matching round complexity of O(D+(ϵ^-1log n)^2) rounds that is suitable for dense graphs. We also show that with the same number of rounds it is possible that each node outputs its mapping according to a bijection which is an approximated isomorphism. We conclude with simple simulation arguments that allow us to obtain essentially tight algorithms with round complexity Õ(D) for special families of sparse graphs.
READ FULL TEXT