2
$\begingroup$

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$.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Oct 15 at 19:03
  • $\begingroup$ 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 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'. $\endgroup$
    – Dan
    Commented Oct 16 at 8:17
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Commented Oct 16 at 11:22
  • 1
    $\begingroup$ I understand your point now. I have edited the problem to clarify this. $\endgroup$
    – Dan
    Commented Oct 17 at 8:26
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Oct 17 at 15:28

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dan
    Commented Oct 18 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.