3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Well there should be some $b$ dependence even though $a$ dominates in this complexity since $a\leq b$. $\endgroup$
    – VS.
    Dec 3, 2019 at 16:51
  • $\begingroup$ Perhaps corollaries $1.4$ and $5.1$ are relevant? $\endgroup$
    – VS.
    Dec 3, 2019 at 16:59
  • 1
    $\begingroup$ 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$. $\endgroup$ Dec 11, 2019 at 16:21

Your Answer

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

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