An inverse problem of lexicographic product of graphs

In graph theory, the lexicographic product or (graph composition) $$G ∙ H$$ of graphs $$G$$ and $$H$$ is a graph such that

• the vertex set of $$G ∙ H$$ is the cartesian product $$V(G) × V(H)$$;
• and any two vertices $$(u,v)$$ and $$(x,y)$$ are adjacent in $$G ∙ H$$ if and only if either $$u$$ is adjacent with $$x$$ in $$G$$ or $$u = x$$ and $$v$$ is adjacent with $$y$$ in $$H$$.

Given two graphs, it is easy to obtain their lexicographic product. However the inverse process does not look so easy.

Recognition problem: Given a graph G, can we guess whether there exist graphs $$G_1$$,...,$$G_k$$ such that $$G=G_1 ∙ ⋯ ∙G_k$$ ?

I read the book "Handbook of product graphs" and wiki, that say that the recognition complexity of lexicographic products is polynomially equivalent to the graph isomorphism problem. But I don't see the corresponding algorithm.

We know that there are already polynomial algorithms for the decomposition of the cartesian product of a graph. But for the lexicographic product, I don't know yet if there is some algorithm or code to implement the decomposition of the lexicographic products of a graph.

• A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics, 12 (2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453
• Feigenbaum, J.; Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045 Jul 25 at 4:51
• @JohnL. Sincere appreciation. I scanned the article quickly. It appears to imply a certain algorithm. Jul 25 at 8:30