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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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