<p>It seems to me that this requires <span class="math-container">$\Omega(n^2)$</span> even if we know that <span class="math-container">$H$</span> is the complete graph, i.e., deciding whether <span class="math-container">$G=E_A\cup E_B$</span> is also the complete graph, equivalently, deciding whether <span class="math-container">$\bar E_A \cap \bar E_B=\emptyset$</span>, because this is precisely the set Disjointness problem.</p>

CC BY-SA 4.0
2024-10-18T09:14:31.523Z
I accept your answer. In retrospect, my clarification makes the problem too easy (the original version I had in mind was actually a promised version, but I thought--without thinking carefully--that the version I asked was hard enough. In any case, thank you for the answer.
Dan
CC BY-SA 4.0
2024-10-17T11:16:59.097Z
2024-10-17T11:16:59.097Z
domotorp
<p><em>Update:</em> After some clarification, the final clarified version turns out to be too simple (see the accepted answer). I'm still interested in the multigraph and promised version mentioned in the comments below.</p>
<hr />
<p>Alice receives two simple undirected graphs <span class="math-container">$G_A=(V, E_A)$</span> and <span class="math-container">$H_A=(V, F_A)$</span>. Similarly, Bob receives <span class="math-container">$G_B=(V, E_B)$</span> and <span class="math-container">$H_B=(V, F_B)$</span></p>
<p>How much communication do Alice and Bob need to communicate in order to check if <span class="math-container">$G=(V,E_A\cup E_B)$</span> is isomorphic to <span class="math-container">$H=(V, F_A\cup F_B)$</span>?</p>
<p>For deterministic protocol, a simple fooling set argument is enough to show <span class="math-container">$\Omega(n^2)$</span> lower bound, where <span class="math-container">$n$</span> is the number of vertices. (This holds even when <span class="math-container">$G$</span> is given to Alice and <span class="math-container">$H$</span> is given to Bob.)</p>
<p>Is it known in the literature that randomized protocols (with two-sided errors allowed) require <span class="math-container">$\Omega(n^2)$</span> communication, or even <span class="math-container">$\omega(n)$</span>? Note that if  <span class="math-container">$G$</span> is given to Alice and <span class="math-container">$H$</span> is given to Bob, there is a simple <span class="math-container">$n \cdot polylog(n)$</span> randomized protocol.</p>
<p>Note: I am also interested in the version where multi-edges are allowed in <span class="math-container">$G$</span> and <span class="math-container">$H$</span>.</p>

CC BY-SA 4.0
2024-10-15T19:03:13.320Z
Is this a promise problem, or how do you ensure that they have a partition? Also, it would be nice to provide a link for the $n polylog(n)$ rnd protocol you mention.
domotorp
CC BY-SA 4.0
2024-10-16T08:17:15.897Z
Thanks for the question. It's not a promised problem. This is a standard set up for graph problems. A deterministic lower bound was claimed in Theorem 6 in https://dl.acm.org/doi/pdf/10.1145/800076.802483 (but with today's understanding, one can just derive this easily via fooling set). For n*polylog(n) protocol, I'm not sure it's published anywhere. The idea is to define the total order among isomorphic graphs. Let G' and H' be the graphs that are minimal in this order that are isomorphic to G and H. Then Alice and Bob just need hashing to check if G'=H'.
Dan
CC BY-SA 4.0
2024-10-16T11:22:47.800Z
A "promise problem" in complexity theory means a problem where the inputs are promised to satisfy some property that the player(s) can(not) check. In your case, the players have no way of knowing that they are indeed given a partition of the graphs, because some edges might be repeated. So what happens if both of them hold the same edge of $G$? Can their output be arbitrary? Or do you rather define $G$ as the union of edges held by the players?
domotorp
CC BY-SA 4.0
2024-10-17T08:26:50.807Z
I understand your point now. I have edited the problem to clarify this.
Dan
CC BY-SA 4.0
2024-10-17T15:28:23.813Z
Interesting problem - curious where you came across it. To me, a more "natural" communication version of GI is that each player gets a graph, and they must communicate to decide whether the two graphs are isomorphic... Not arguing against your version, just curious how/where it arises.
Joshua Grochow
CC BY-SA 4.0
2024-10-18T09:19:24.993Z
@JoshuaGrochow: I'm actually just curious about the communication complexity of this problem in general. Since the "natural" version is too easy, I thought the version I asked (both the one that got answered already, the multi-graph version, and the promise version) should have been studied, but I couldn't find anything in the literature. By the way, the promised version would be how I interpret the way Yao defined the problem in https://dl.acm.org/doi/pdf/10.1145/800076.802483.
Dan
<communication-complexity><graph-isomorphism>
Communication complexity of graph isomorphism with 2-sided error
Dan
# Communication complexity of graph isomorphism with 2-sided error

(Asked by: username_0 on 2024-10-14)

*Update:* After some clarification, the final clarified version turns out to be too simple (see the accepted answer). I'm still interested in the multigraph and promised version mentioned in the comments below.

---

Alice receives two simple undirected graphs $G\_A=(V, E\_A)$ and $H\_A=(V, F\_A)$. Similarly, Bob receives $G\_B=(V, E\_B)$ and $H\_B=(V, F\_B)$

How much communication do Alice and Bob need to communicate in order to check if $G=(V,E\_A\cup E\_B)$ is isomorphic to $H=(V, F\_A\cup F\_B)$?

For deterministic protocol, a simple fooling set argument is enough to show $\Omega(n^2)$ lower bound, where $n$ is the number of vertices. (This holds even when $G$ is given to Alice and $H$ is given to Bob.)

Is it known in the literature that randomized protocols (with two-sided errors allowed) require $\Omega(n^2)$ communication, or even $\omega(n)$? Note that if $G$ is given to Alice and $H$ is given to Bob, there is a simple $n \cdot polylog(n)$ randomized protocol.

Note: I am also interested in the version where multi-edges are allowed in $G$ and $H$.

**Tags:** communication-complexity, graph-isomorphism

> **Comments:**
> **username_1**: Is this a promise problem, or how do you ensure that they have a partition? Also, it would be nice to provide a link for the $n polylog(n)$ rnd protocol you mention.  
> **username_0**: Thanks for the question. It's not a promised problem. This is a standard set up for graph problems. A deterministic lower bound was claimed in Theorem 6 in https://dl.acm.org/doi/pdf/10.1145/800076.802483 (but with today's understanding, one can just derive this easily via fooling set). For n*polylog(n) protocol, I'm not sure it's published anywhere. The idea is to define the total order among isomorphic graphs. Let G' and H' be the graphs that are minimal in this order that are isomorphic to G and H. Then Alice and Bob just need hashing to check if G'=H'.  
> **username_1**: A "promise problem" in complexity theory means a problem where the inputs are promised to satisfy some property that the player(s) can(not) check. In your case, the players have no way of knowing that they are indeed given a partition of the graphs, because some edges might be repeated. So what happens if both of them hold the same edge of $G$? Can their output be arbitrary? Or do you rather define $G$ as the union of edges held by the players?  
> **username_0**: I understand your point now. I have edited the problem to clarify this.  
> **username_2**: Interesting problem - curious where you came across it. To me, a more "natural" communication version of GI is that each player gets a graph, and they must communicate to decide whether the two graphs are isomorphic... Not arguing against your version, just curious how/where it arises.  
> **username_0**: @JoshuaGrochow: I'm actually just curious about the communication complexity of this problem in general. Since the "natural" version is too easy, I thought the version I asked (both the one that got answered already, the multi-graph version, and the promise version) should have been studied, but I couldn't find anything in the literature. By the way, the promised version would be how I interpret the way Yao defined the problem in https://dl.acm.org/doi/pdf/10.1145/800076.802483.  

---

## 1 answers

### Answer by username_1 on 2024-10-17. Score: 2 | Accepted answer

It seems to me that this requires $\Omega(n^2)$ even if we know that $H$ is the complete graph, i.e., deciding whether $G=E\_A\cup E\_B$ is also the complete graph, equivalently, deciding whether $\bar E\_A \cap \bar E\_B=\emptyset$, because this is precisely the set Disjointness problem.

> **Comments:**
> **username_0**: I accept your answer. In retrospect, my clarification makes the problem too easy (the original version I had in mind was actually a promised version, but I thought--without thinking carefully--that the version I asked was hard enough. In any case, thank you for the answer.  

---

