25
$\begingroup$

This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.

There are various graph products, and I'm interested in any of them here. What is the complexity of determining whether a graph $K$ is isomorphic to a non-trivial product? (Certainly for the Cartesian product, $K = K \square 1$ where $1$ is the graph with one vertex.)

I've looked at the pages "factor graph" and "graph factorization" on Wikipedia, but neither seem to be related. Is this problem known under another name?

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think this answer is better than mine. $\endgroup$ – Yota Otachi Mar 31 '12 at 11:55
15
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I accepted @someone's answer, but thank you for the extra information. $\endgroup$ – Max Apr 2 '12 at 8:03
12
$\begingroup$

There is a linear-time algorithm for determining the prime factors of connected graphs with respect to the Cartesian product. See the paper by Imrich and Peterin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.