论文标题
在交流模型中的图形同构的分布式测试
Distributed Testing of Graph Isomorphism in the CONGEST model
论文作者
论文摘要
在本文中，我们研究了在交货分布模型中测试图形同构（GI）的问题。在这种情况下，我们测试分布网络$ g_u $是同构对$ g_k $的同构，它是对网络中所有节点的输入，还是仅对单个节点。 我们首先考虑算法区分$ g_u $和$ g_k $的问题的决策变体，这些算法与$ g_u $和$ g_k $的$ g_k $和$ g_k $不是同构。我们为$ o（n）$ rounds提供了随机算法，用于仅给出一个节点的$ g_k $的设置。我们证明，对于此设置，任何确定性算法的回合数为$ \tildeΩ（n^2）$ rounds，其中$ n $表示节点的数量，这意味着决定GI的随机和确定性复杂性之间的分离。 然后，我们考虑该问题的\ emph {属性测试}变体，其中仅需要算法来区分$ g_u $和$ g_k $与$ g_u $和$ g_u $和$ g_k $ asph \ emph {far}与isomorphic（根据某些预定距离的距离的距离）的情况。我们表明，每种算法都需要$ω（d）$ rounds，其中$ d $表示网络的直径。即使将所有节点均给出了$ g_k $作为输入，即使消息大小是无限的，该下限也可以保留。我们提供了一种随机算法，其几乎匹配的圆形复杂度为$ O（d+（ε^{ - 1} \ log n）^2）$ rounds，适用于密集图。 我们还表明，使用相同数量的回合，每个节点可能会根据\ emph {近似}同构的生物映射输出其映射。 我们以简单的仿真论点结束，使我们能够获得具有圆形复杂性的基本紧密算法$ \ tilde {o}（d）$，用于稀疏图的特殊系列。
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 $\tildeΩ(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 $Ω(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+(ε^{-1}\log 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 $\tilde{O}(D)$ for special families of sparse graphs.
