8
$\begingroup$

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.

Now it feels to me that this class of graphs is "too rich" for there to be an efficient isomorphism algorithm yet I don't see any easy argument that this problem is GI-complete. The subclassess of bipartite graphs that are proven to be GI-complete do not seem to match this class.

Hence I am wondering

Given two induced subgraphs of order $k$ that are induced subgraphs of $Q_n$ is there a polynomial algorithm (in $k$) to decide whether they are isomorphic?

A relaxation of the above question that is also of interest is

Given two colored hypercubes of dimension $n$ can we decide if they are isomorphic in time polynomial in $2^n$?

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you given the embeddings in the hypercube, or just abstract graphs? $\endgroup$
    – Brendan McKay
    Commented May 26, 2015 at 12:40
  • $\begingroup$ Both questions are of interest but in this specific case the embeddings are given. I have edited the question accordingly. $\endgroup$
    – Jernej
    Commented May 26, 2015 at 12:48
  • $\begingroup$ A simpler question, more likely to be polynomial time, is whether the two graphs are isomorphic by a symmetry of the hypercube. $\endgroup$
    – Brendan McKay
    Commented May 27, 2015 at 3:40
  • $\begingroup$ @BrendanMcKay Hm.. Wouldn't that then be polynomially equivalent to the problem of finding an isomorphism between colored hypercubes or am I missing something and this is in fact a harder problem? $\endgroup$
    – Jernej
    Commented May 27, 2015 at 8:26
  • $\begingroup$ You are right about the equivalence. I don't know what the complexity is. $\endgroup$
    – Brendan McKay
    Commented May 27, 2015 at 9:14

2 Answers 2

Reset to default
1
$\begingroup$

I think this problem is GI-complete. One way to show that would be to "embed" an arbitrary graph $G$ into $Q_n$; then any solution to the problem above would provide a solution to GI.

We cannot literally embed an arbitrary graph in $Q_n$ (because, for instance, any embedding would be bipartite), but if we replace the edges of the target graph with connected paths of some fixed length $L$, then we can find an embedding whose minor matches $G$, and for whom the GI problem is equivalent (since both graphs will use the same $L$).

At this point, there is a trivial solution. Label the nodes of $G$ as $1,...,k$, let $e_i$ be the vector of that is all zero except for a single 1 in the i-th place. Each binary string is also associated with a node of $Q_k$ in the natural way. Associate node $i$ of $G$ with $e_i$. Then we can build a non-overlapping path between any $e_i$ and $e_j$ of length $L=2$ by traveling via node $e_i+e_j$.

Unfortunately, this requires $n=k$; I imagine you'd prefer $n=O(poly(\log(k)))$. I think a combination of binary trees and rearrangeable networks should allow such a construction, but I cannot seem to get it working correctly.

For an introduction to the relevant kinds of constructions, a good starting point might be Leighton's "Introduction to Parallel Algorithms..." (1991).

Improve this answer
$\endgroup$
0
1
$\begingroup$

For the "relaxation" to embedding-preserving isomorphisms, note that the $n$-cube has only $2^n n!$ symmetries, so you can try them all in $2^{2n} n!$ time or a little less. That's a lot if only a small fraction of the $N=2^n$ vertices are coloured, but if a large fraction are coloured the bound becomes $N^{O(\log\log N)}$, which is a lot faster than any known GI-complete problem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .