<p>If you are willing to relax the 2 to some other constant, then yes: this can be solved in <span class="math-container">$O(c^a)$</span> time for some absolute constant <span class="math-container">$c$</span>. You can view this problem as isomorphism of hypergraphs, where the vertices in <span class="math-container">$A_i$</span> are the vertices of your hypergraph, and the vertices in <span class="math-container">$B_i$</span> are hyperedges. <a href="https://doi.org/10.1145/301250.301427" rel="nofollow noreferrer">Luks (STOC '99)</a> showed how to solve hypergraph isomorphism for hypregraphs on <span class="math-container">$a$</span> vertices in <span class="math-container">$O(c^a)$</span> time for some absolute constant <span class="math-container">$c$</span>.</p>

CC BY-SA 4.0
2019-12-03T16:51:32.880Z
Well there should be some $b$ dependence even though $a$ dominates in this complexity since $a\leq b$.
VS.
CC BY-SA 4.0
2019-12-03T16:59:26.530Z
Perhaps corollaries $1.4$ and $5.1$ are relevant?
VS.
CC BY-SA 4.0
2019-12-11T16:21:39.613Z
The dependence on $b$ is only $b^k$ (possible even just linear in $b$, but I'd have to think a little more about that). Since $b \leq 2^a$ WLOG (otherwise there are two vertices in $B_i$ with identical neighborhoods, which we can collapse and keep track of their multiplicity by a small additional piece of data), we get that $b^k \leq c^a$ for some constant $c$.
Joshua Grochow
CC BY-SA 4.0
2019-12-03T16:49:30.083Z
2019-12-03T16:49:30.083Z
Joshua Grochow
<p>For <span class="math-container">$i=1,2$</span>, let <span class="math-container">$G_i=(A_i\cup B_i,E_i)$</span> be an undirected bipartite 
graph with bipartition <span class="math-container">$A_i$</span> and <span class="math-container">$B_i$</span>, where <span class="math-container">$|A_1|=|A_2|=a$</span> and 
<span class="math-container">$|B_1|=|B_2|=b$</span> with <span class="math-container">$a\le b$</span>.</p>

<blockquote>
  <p><strong>Question.</strong> Is the problem of deciding isomorphism between 
  such graphs solvable in <span class="math-container">$O(b^k 2^a)$</span> time, for some constant <span class="math-container">$k&gt;0$</span>?</p>
</blockquote>

<p>Note that Babai's result yields a <span class="math-container">$2^{(\log(a+b))^c}$</span> time 
algorithm for some constant <span class="math-container">$c&gt;1$</span>. 
For the cases with <span class="math-container">$a=O(\log b)$</span>, a solution to my question would
yield a polynomial time complexity.</p>

<time-complexity><graph-isomorphism>
Complexity of unbalanced bipartite isomorphism
VS.
# Complexity of unbalanced bipartite isomorphism

(Asked by: username_0 on 2019-12-03)

For $i=1,2$, let $G\_i=(A\_i\cup B\_i,E\_i)$ be an undirected bipartite
graph with bipartition $A\_i$ and $B\_i$, where $|A\_1|=|A\_2|=a$ and
$|B\_1|=|B\_2|=b$ with $a\le b$.

> **Question.** Is the problem of deciding isomorphism between
> such graphs solvable in $O(b^k 2^a)$ time, for some constant $k>0$?

Note that Babai's result yields a $2^{(\log(a+b))^c}$ time
algorithm for some constant $c>1$.
For the cases with $a=O(\log b)$, a solution to my question would
yield a polynomial time complexity.

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

---

## 1 answers

### Answer by username_1 on 2019-12-03. Score: 3 | Accepted answer

If you are willing to relax the 2 to some other constant, then yes: this can be solved in $O(c^a)$ time for some absolute constant $c$. You can view this problem as isomorphism of hypergraphs, where the vertices in $A\_i$ are the vertices of your hypergraph, and the vertices in $B\_i$ are hyperedges. [Luks (STOC '99)](https://doi.org/10.1145/301250.301427) showed how to solve hypergraph isomorphism for hypregraphs on $a$ vertices in $O(c^a)$ time for some absolute constant $c$.

> **Comments:**
> **username_0**: Well there should be some $b$ dependence even though $a$ dominates in this complexity since $a\leq b$.  
> **username_0**: Perhaps corollaries $1.4$ and $5.1$ are relevant?  
> **username_1**: The dependence on $b$ is only $b^k$ (possible even just linear in $b$, but I'd have to think a little more about that). Since $b \leq 2^a$ WLOG (otherwise there are two vertices in $B_i$ with identical neighborhoods, which we can collapse and keep track of their multiplicity by a small additional piece of data), we get that $b^k \leq c^a$ for some constant $c$.  

---

