Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Equally interesting would be to learn about such problems with a non-trivial proof of polytime complexity. Is there anything well-known besides the graph factoring problem?