Esta pregunta surge por pura curiosidad (surgió mientras pensaba en desarmar una cadena , pero no estoy seguro de si realmente está relacionada), así que espero que sea apropiada.
Hay varios productos gráficos, y estoy interesado en alguno de ellos aquí. ¿Cuál es la complejidad de determinar si un gráfico es isomorfo a un producto no trivial? (Ciertamente para el producto cartesiano, donde es el gráfico con un vértice).K = K ◻ 1 1
He visto las páginas "gráfico de factores" y "factorización de gráficos" en Wikipedia, pero ninguna parece estar relacionada. ¿Se conoce este problema con otro nombre?
Se pueden reconocer varios productos gráficos en tiempo polinómico. Como de costumbre, el producto cartesiano es el más fácil, y el caso cartesiano también es la base de los algoritmos para varios otros productos. El reconocimiento del producto lexicográfico (composición) es equivalente al isomorfismo gráfico.
Con más detalle:
Sea la clase de gráficos simples finitos y la clase de gráficos simples finitos que pueden tener bucles automáticos. (Claramente .)Γ 0 Γ ⊂ Γ 0Γ Γ0 Γ⊂Γ0
Decidir si un gráfico de entrada conectado tiene factores en se puede hacer en tiempo polinómico para los productos cartesianos y fuertes, y también para el producto directo cuando no es bipartito. Decidir si tiene factores en está en tiempo polinómico para el producto cartesiano, pero es poco probable que esté en tiempo polinómico para el producto lexicográfico. No sé el estado de decidir si tiene factores en para los productos directos y fuertes.Γ 0 G G Γ G ΓG Γ0 G G Γ G Γ
Resultados relevantes de Imrich y Klavžar:
El resultado para el producto cartesiano se mejora luego a tiempo y espacio en el Capítulo 7. Como se señaló en otras respuestas, esto se ha mejorado a tiempo lineal.O ( m )O(mlogn) O(m)
Para el producto lexicográfico:
Entonces, decidir si un gráfico es primo con respecto al producto lexicográfico es equivalente al ISOMORFISMO GRÁFICO, con respecto a las reducciones de Turing.
El caso del producto directo y fuerte que tiene factores sin auto-bucles parece estar ausente de las referencias que he visto. Agradecería cualquier sugerencia a los documentos que discutan este caso, o una pista de por qué no es interesante.
fuente
Existe un algoritmo de tiempo lineal para determinar los factores primos de los gráficos conectados con respecto al producto cartesiano. Ver el artículo de Imrich y Peterin.
fuente