Finding the Prime Factors of Strong Direct Product Graphs in Polynomial Time
The strong direct product is one of several standard product operators on graphs. McKenzie [Fund. Math. LXX(1971), 59-101] showed that any connected graph has a unique prime factorization under the strong direct product. We give a polynomial-time algorithm for finding this unique factorization, thus settling a question of Nesetril.