# Complexity of unbalanced bipartite isomorphism

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.

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) showed how to solve hypergraph isomorphism for hypregraphs on $$a$$ vertices in $$O(c^a)$$ time for some absolute constant $$c$$.
• Well there should be some $b$ dependence even though $a$ dominates in this complexity since $a\leq b$.
• Perhaps corollaries $1.4$ and $5.1$ are relevant?
• 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$. Dec 11, 2019 at 16:21