Distributed Testing of Graph Isomorphism in the CONGEST Model.

DOI10.4230/LIPICS.APPROX/RANDOM.2020.19MaRDI QIDQ6084362zbMATH OpenOpenAlexFDO

Publication date 31 October 2023

Full work available at URL https://arxiv.org/abs/2003.00468

graph algorithms graph isomorphism distributed decision distributed property testing the CONGEST model

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: 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

i l d e O m e g a (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 emph{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 emph{far} from being isomorphic (according to some predetermined distance measure). We show that every algorithm requires

O m e g a (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 + (e p s i l o n^{- 1} l o g 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 emph{approximated} isomorphism. We conclude with simple simulation arguments that allow us to obtain essentially tight algorithms with round complexity

i l d e O (D)

for special families of sparse graphs.

Cites work

This page was built for publication: Distributed Testing of Graph Isomorphism in the CONGEST Model.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6084362)