Isomorphism problem on the class of induced subgraphs of a hypercube 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$?

 A: 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).
A: 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.
