Complexidade de "é um gráfico um produto"

Essa questão surge da pura curiosidade (surgiu quando pensamos em embaralhar uma string , mas não tenho certeza se ela está realmente relacionada), por isso espero que seja apropriado.

Existem vários produtos gráficos e estou interessado em qualquer um deles aqui. Qual é a complexidade de determinar se um gráfico é isomórfico para um produto não trivial? (Certamente para o produto cartesiano, K = K ◻ 1 onde 1 é o gráfico com um vértice.)$K$$K = K \square 1$$1$

Eu olhei as páginas "fator gráfico" e "fatoração gráfica" na Wikipedia, mas nenhuma delas parece estar relacionada. Esse problema é conhecido com outro nome?

Veja o artigo Wilfried, Imrich; Iztok, Peterin, Reconhecendo produtos cartesianos em tempo linear . Discrete Math., 307, 3-5, Página (s): 472--483, 2007. Penso que Imrich tem mais artigos para outros produtos.

Vários produtos gráficos podem ser reconhecidos em tempo polinomial. Como sempre, o produto cartesiano é o mais fácil, e o caso cartesiano também é a base para os algoritmos de vários outros produtos. O reconhecimento do produto lexicográfico (composição) é equivalente ao isomorfismo gráfico.

Em mais detalhes:

$\Gamma$$\Gamma_0$$\Gamma \subset \Gamma_0$

$G$$\Gamma_0$$G$$G$$\Gamma$$G$$\Gamma$

Resultados relevantes de Imrich e Klavžar:

$G$$n$$m$$O(mn)$$O(m)$

$\Gamma_0$

$O(m\log n)$$O(m)$

Para o produto lexicográfico:

Teorema 6.20. O problema de decisão sobre se um dado gráfico conectado é primo em relação ao produto lexicográfico é pelo menos tão difícil quanto o problema de isomorfismo do gráfico.

$n$$n$

Portanto, decidir se um gráfico é primordial em relação ao produto lexicográfico é equivalente ao ISOMORFISMO GRÁFICO, em relação às reduções de Turing.

O caso do produto direto e forte com fatores sem auto-loop parece estar ausente das referências que observei. Agradeço qualquer indicação de trabalhos que discutam esse caso, ou uma dica de por que é desinteressante.

• Wilfried Imrich e Sandi Klavžar, Gráficos de produtos: Estrutura e reconhecimento . Wiley, 2000. ISBN 0-471-37039-8.

Existe um algoritmo de tempo linear para determinar os fatores primos dos gráficos conectados em relação ao produto cartesiano. Veja o artigo de Imrich e Peterin.