Complexity of "is a graph a product"
Check the paper Wilfried, Imrich; Iztok, Peterin, Recognizing Cartesian products in linear time. Discrete Math., 307, 3-5, Page(s): 472--483, 2007. I think that Imrich has more papers for other products.