Búsqueda eficiente de un ciclo de 5 en un grafo disperso.

Question

Hola,

Estaba leyendo este hilo: Encontrar un ciclo de longitud fija

Quiero encontrar un 5-ciclo en un gráfico. En realidad, lo que realmente quiere es un ciclo impar más corto de una duración mínima de 5, pero quizá eso no venga al caso. Para mis fines, trato $m$ y $n$ lo mismo en el análisis de la complejidad.

¿Podemos hacer algo mejor que un código de colores para encontrar un 5-ciclo en este caso? Permítanme dar una formulación específica de mi pregunta:

¿Cuál es el mínimo $\alpha$ tal que existe un $O(m^\alpha)$ -algoritmo para detectar un ciclo de longitud 5? ¿En qué consiste el algoritmo? ¿Y qué es $\alpha$ si prohíbe métodos poco prácticos como la multiplicación rápida de matrices Coppersmith-Winograd?

Answer 1

Este artículo trata de la detección de ciclos cortos.

http://people.clarkson.edu/~ebollt/Papers/LComm.pdf

Si no responde por completo a su pregunta, tal vez pueda servirle de límite o como punto de partida para una búsqueda bibliográfica más profunda.