Several graph products can be recognized in polynomial time. As usual the Cartesian product is the easiest, and the Cartesian case is also the basis for the algorithms for several other products. Recognition of the lexicographic product (composition) is equivalent to graph isomorphism.
In more detail:
Let $\Gamma$ be the class of finite simple graphs, and $\Gamma_0$ be the class of finite simple graphs which may have self-loops. (Clearly $\Gamma \subset \Gamma_0$.)
Deciding if a connected input graph $G$ has factors in $\Gamma_0$ can be done in polynomial time for the Cartesian and strong products, and also for the direct product when $G$ is non-bipartite.
Deciding if $G$ has factors in $\Gamma$ is in polynomial time for the Cartesian product, but is unlikely to be in polynomial time for the lexicographic product.
I do not know the status of deciding if $G$ has factors in $\Gamma$ for the direct and strong products.
Relevant results from Imrich and Klavžar:
Theorem 4.10. For a connected graph $G$ on $n$ vertices and $m$ edges one can find the prime factorization with respect to the Cartesian product in $O(mn)$ time using $O(m)$ space.
Theorem 5.43. The prime factor decomposition of connected, nonbipartite graphs in $\Gamma_0$ with respect to the direct product and of connected simple graphs with respect to the strong product can be determined in polynomial time.
The result for Cartesian product is then improved to $O(m\log n)$ time and $O(m)$ space in Chapter 7. As pointed out in other answers, this has since been improved to linear time.
For the lexicographic product:
Theorem 6.20. The decision problem whether a given connected graph is prime with respect to the lexicographic product is at least as difficult as the graph isomorphism problem.
Theorem 6.21. The decision problem whether a given connected graph is prime with respect to the lexicographic product is not more difficult than the solution of a polynomial number (in $n$) of graph isomorphism problems, the size of each of which is also polynomial in $n$.
So deciding whether a graph is prime with respect to the lexicographic product is equivalent to GRAPH ISOMORPHISM, with respect to Turing reductions.
The case of the direct and strong product having factors without self-loops seems to be absent from the references I have looked at. I would appreciate any pointers to papers that do discuss this case, or a hint why it is uninteresting.
- Wilfried Imrich and Sandi Klavžar, Product Graphs: Structure and Recognition. Wiley, 2000. ISBN 0-471-37039-8.
