<p>There is a linear-time algorithm for determining the prime factors of connected graphs with respect to the Cartesian product. See the <a href="http://dx.doi.org/10.1016/j.disc.2005.09.038">paper</a> by Imrich and Peterin.</p>

CC BY-SA 3.0
2012-03-30T11:00:38.627Z
2012-03-30T11:00:38.627Z
Yota Otachi
<p>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.</p>
<hr />
<p>In more detail:</p>
<p>Let <span class="math-container">$\Gamma$</span> be the class of finite simple graphs, and <span class="math-container">$\Gamma_0$</span> be the class of finite simple graphs which may have self-loops.  (Clearly <span class="math-container">$\Gamma \subset \Gamma_0$</span>.)</p>
<p>Deciding if a connected input graph <span class="math-container">$G$</span> has factors in <span class="math-container">$\Gamma_0$</span> can be done in polynomial time for the Cartesian and strong products, and also for the direct product when <span class="math-container">$G$</span> is non-bipartite.
Deciding if <span class="math-container">$G$</span> has factors in <span class="math-container">$\Gamma$</span> 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 <span class="math-container">$G$</span> has factors in <span class="math-container">$\Gamma$</span> for the direct and strong products.</p>
<p>Relevant results from Imrich and Klavžar:</p>
<blockquote>
<p>Theorem 4.10.  For a connected graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges one can find the prime factorization with respect to the Cartesian product in <span class="math-container">$O(mn)$</span> time using <span class="math-container">$O(m)$</span> space.</p>
<p>Theorem 5.43. The prime factor decomposition of connected, nonbipartite graphs in <span class="math-container">$\Gamma_0$</span> with respect to the direct product and of connected simple graphs with respect to the strong product can be determined in polynomial time.</p>
</blockquote>
<p>The result for Cartesian product is then improved to <span class="math-container">$O(m\log n)$</span> time and <span class="math-container">$O(m)$</span> space in Chapter 7.  As pointed out in other answers, this has since been improved to linear time.</p>
<p>For the lexicographic product:</p>
<blockquote>
<p>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.</p>
<p>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 <span class="math-container">$n$</span>) of graph isomorphism problems, the size of each of which is also polynomial in <span class="math-container">$n$</span>.</p>
</blockquote>
<p>So deciding whether a graph is prime with respect to the lexicographic product is equivalent to GRAPH ISOMORPHISM, with respect to Turing reductions.</p>
<p>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.</p>
<ul>
<li>Wilfried Imrich and Sandi Klavžar, <em>Product Graphs: Structure and Recognition</em>. Wiley, 2000.  ISBN 0-471-37039-8.</li>
</ul>

CC BY-SA 3.0
2012-04-02T08:03:22.867Z
I accepted @someone's answer, but thank you for the extra information.
Max
CC BY-SA 3.0
2012-04-01T16:58:25.457Z
2012-04-03T11:44:34.257Z
2020-06-17T09:38:08.363Z
András Salamon
<p>Check the paper Wilfried, Imrich; Iztok, Peterin, <a href="http://dx.doi.org/10.1016/j.disc.2005.09.038">Recognizing Cartesian products in linear time</a>. Discrete Math., 307, 3-5, Page(s): 472--483, 2007. I think that Imrich has more papers for other products.</p>

CC BY-SA 3.0
2012-03-31T11:55:29.887Z
I think this answer is better than mine.
Yota Otachi
CC BY-SA 3.0
2012-03-30T10:51:03.693Z
2012-04-03T04:07:28.953Z
2012-04-03T04:07:28.953Z
someone
<p>This question arises out of pure curiosity (it came up while thinking about <a href="https://cstheory.stackexchange.com/q/34/2241">unshuffling a string</a>, but I'm not sure if it's actually related) so I hope it's appropriate.</p>

<p>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.)</p>

<p>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?</p>

<cc.complexity-theory><graph-algorithms>
Complexity of "is a graph a product"
Max
# Complexity of "is a graph a product"

(Asked by: username_0 on 2012-03-30)

This question arises out of pure curiosity (it came up while thinking about [unshuffling a string](https://cstheory.stackexchange.com/q/34/2241), 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?

**Tags:** cc.complexity-theory, graph-algorithms


---

## 3 answers

### Answer by username_3 on 2012-03-30. Score: 20 | Accepted answer

Check the paper Wilfried, Imrich; Iztok, Peterin, [Recognizing Cartesian products in linear time](http://dx.doi.org/10.1016/j.disc.2005.09.038). Discrete Math., 307, 3-5, Page(s): 472--483, 2007. I think that Imrich has more papers for other products.

> **Comments:**
> **username_1**: I think this answer is better than mine.  

---

### Answer by username_2 on 2012-04-01. Score: 15

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.

> **Comments:**
> **username_0**: I accepted @username_3's answer, but thank you for the extra information.  

---

### Answer by username_1 on 2012-03-30. Score: 12

There is a linear-time algorithm for determining the prime factors of connected graphs with respect to the Cartesian product. See the [paper](http://dx.doi.org/10.1016/j.disc.2005.09.038) by Imrich and Peterin.


---

