<p>This is open and at least as hard as the Graph Automorphism problem. If G,H have no nontrivial automorphisms (aka rigid), then N(G,H)=0 or 1, so even N(G,H) mod 2 solves the promise problem RigidGI. The Graph Automorphism problem polynomial-time Turing reduces to RigidGI.* So RigidGI is at least as hard as GA, which, while not known to be equivalent to GI, is still not known to be in P (in fact, I am not sure that currently any better bounds are known for GA than are known for GI).</p>
<p>By a little trick, this reduction can even be made &quot;smart&quot; in the sense of <a href="https://doi.org/10.1137/0217018" rel="nofollow noreferrer">Grollman &amp; Selman</a>, meaning that it only ever queries instances that satisfy the promise, see Allender-G.-Moore-van Melkebeek-Morgan <a href="https://eccc.weizmann.ac.il/report/2015/162/" rel="nofollow noreferrer">&quot;A note on Graph Automorphism and Smart Reductions&quot;</a></p>
<p>* The proof is similar to that of Theorem 1.31 in <a href="https://doi.org/10.1007/978-1-4612-0333-9" rel="nofollow noreferrer">Köbler, Schöning, and Torán</a>, except instead of the union of two copies of the graph as in their proof, the reduction asks about whether those two copies are isomorphic to one another. Contrary to my comment above, RigidGI and GA aren't known to be equivalent; sorry for my confusion, I was thinking of the non-promise decision problem UniqueGA defined as the set of graphs with exactly one nontrivial automorphism - UniqueGA and GA are indeed poly-time Turing equivalent.)</p>

CC BY-SA 4.0
2024-07-15T23:02:21.050Z
By Mathon's result #GI mod 2 reduces to GI (https://www.sciencedirect.com/science/article/abs/pii/0020019079900048).
Turbo
CC BY-SA 4.0
2024-07-15T23:46:09.000Z
Yes, #GI is poly-time Turing equivalent to GI, so #GI mod 2 is no harder than GI, and hence (by what I said in my answer) #GI mod 2 sits (weakly, not nec. strictly) in between GA and GI, or even between RigidGI and GI.
Joshua Grochow
CC BY-SA 4.0
2024-07-15T21:37:31.160Z
2024-07-15T21:37:31.160Z
Joshua Grochow
<p>Given graphs <span class="math-container">$G,H$</span> let <span class="math-container">$N(G,H)$</span> be the number of isomorphisms between them. Is there polynomial time algorithm to compute <span class="math-container">$N(G,H)\bmod 2^t$</span> for every fixed <span class="math-container">$t\geq1$</span>?</p>

CC BY-SA 4.0
2024-06-28T16:05:30.320Z
If G,H are rigid (no automorphisms), then N(G,H)=0 or 1, so even N(G,H) mod 2 tells you isomorphism for the promise problem RigidGI, which is equivalent to GA. So, maybe easier than GI, but not known to be in P.
Joshua Grochow
<ds.algorithms><graph-theory><time-complexity><graph-isomorphism><parity>
Is parity of GI easy?
Turbo
# Is parity of GI easy?

(Asked by: username_0 on 2024-06-28)

Given graphs $G,H$ let $N(G,H)$ be the number of isomorphisms between them. Is there polynomial time algorithm to compute $N(G,H)\bmod 2^t$ for every fixed $t\geq1$?

**Tags:** ds.algorithms, graph-theory, time-complexity, graph-isomorphism, parity
> **Comments:**
> **username_1**: If G,H are rigid (no automorphisms), then N(G,H)=0 or 1, so even N(G,H) mod 2 tells you isomorphism for the promise problem RigidGI, which is equivalent to GA. So, maybe easier than GI, but not known to be in P.  

---

## 1 answers

### Answer by username_1 on 2024-07-15. Score: 4 | Accepted answer

This is open and at least as hard as the Graph Automorphism problem. If G,H have no nontrivial automorphisms (aka rigid), then N(G,H)=0 or 1, so even N(G,H) mod 2 solves the promise problem RigidGI. The Graph Automorphism problem polynomial-time Turing reduces to RigidGI.\* So RigidGI is at least as hard as GA, which, while not known to be equivalent to GI, is still not known to be in P (in fact, I am not sure that currently any better bounds are known for GA than are known for GI).

By a little trick, this reduction can even be made "smart" in the sense of [Grollman & Selman](https://doi.org/10.1137/0217018), meaning that it only ever queries instances that satisfy the promise, see Allender-G.-Moore-van Melkebeek-Morgan ["A note on Graph Automorphism and Smart Reductions"](https://eccc.weizmann.ac.il/report/2015/162/)

\* The proof is similar to that of Theorem 1.31 in [Köbler, Schöning, and Torán](https://doi.org/10.1007/978-1-4612-0333-9), except instead of the union of two copies of the graph as in their proof, the reduction asks about whether those two copies are isomorphic to one another. Contrary to my comment above, RigidGI and GA aren't known to be equivalent; sorry for my confusion, I was thinking of the non-promise decision problem UniqueGA defined as the set of graphs with exactly one nontrivial automorphism - UniqueGA and GA are indeed poly-time Turing equivalent.)

> **Comments:**
> **username_0**: By Mathon's result #GI mod 2 reduces to GI (https://www.sciencedirect.com/science/article/abs/pii/0020019079900048).  
> **username_1**: Yes, #GI is poly-time Turing equivalent to GI, so #GI mod 2 is no harder than GI, and hence (by what I said in my answer) #GI mod 2 sits (weakly, not nec. strictly) in between GA and GI, or even between RigidGI and GI.  

---

