0
$\begingroup$

Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that given graph G is constructed from a p-dimension hypercube graph Hp of 2n vertices [ so n is a power of 2 ] as ...

Since hypercube is always bipartite.[ Hp = (L,R),V ]
G has n nodes corresponding to the left set L of Hp.
For any 2 nodes in L which have a path of length 2 in Hp, there is an edge between the corresponding nodes in G.

It is easy to see that G is regular and highly symmetric [in term diameter,no of diameters etc due to properties of hypergraph ].

My problem is how to detect whether the input graph can be constructed from a hypercube graph as shown or not . i.e. efficiently check for isomorphism.

Note For a given (n,k) there can be many regular graph as shown in http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

|cite|improve this question
$\endgroup$
  • 10
    $\begingroup$ If you really know that graph isomorphism is NP-hard, your knowledge vastly surpasses the rest of humanity. $\endgroup$ – Emil Jeřábek supports Monica Dec 9 '14 at 19:42
  • 1
    $\begingroup$ Our of curiosity, what is the motivation behind this question? $\endgroup$ – Tsuyoshi Ito Dec 9 '14 at 21:53
  • $\begingroup$ @EmilJeřábek , sorry for my bad mistake, I have corrected it. $\endgroup$ – v78 Dec 10 '14 at 3:26
2
$\begingroup$

If $p$ is fixed, graph isomorphism can be tested in polynomial time, see [E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982].

|cite|improve this answer
$\endgroup$

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.