Encontrar un ciclo de longitud fija

Question

¿Existe algún resultado sobre la complejidad temporal de encontrar un ciclo de longitud fija $k$ en un gráfico general? Todo lo que sé es que Alon, Yuster y Zwick utilizan una técnica llamada "código de colores", que tiene un tiempo de ejecución de $O(M(n))$ donde $n$ es el número de vértices del grafo de entrada y $M(n)$ es el tiempo necesario para multiplicar dos $n \times n$ matrices.

¿Hay algún resultado mejor?

Answer 1

Encontrar un ciclo de cualquier incluso longitud puede encontrarse en $O(n^2)$ tiempo, que es menor que cualquier límite conocido en $O(M(n))$ . Por ejemplo, un ciclo de longitud cuatro puede encontrarse en $O(n^2)$ tiempo mediante el siguiente procedimiento sencillo:

Supongamos que el conjunto de vértices es $\{1,...,n\}$ . Prepare un $n$ x $n$ matriz $A$ que inicialmente es todo ceros. Para todos los vértices $i$ y todos los pares de vértices $j, k$ que son vecinos de $i$ comprobar $A[j,k]$ para un $1$ . Si tiene un $1$ salida cuatro ciclos en caso contrario $A[j,k]$ ser $1$ . Cuando este bucle finaliza, la salida sin cuatro ciclos .

El algoritmo anterior se ejecuta como máximo en $O(n^2)$ tiempo, ya que para cada triple $i,j,k$ damos la vuelta a $0$ a $1$ en $A$ o nos detenemos. (Suponemos que el grafo está en representación de lista de adyacencia, por lo que es fácil seleccionar pares de vecinos de un vértice).

El caso general es tratado por Raphy Yuster y Uri Zwick en el documento:

Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J. Discrete Math. 10(2): 209-222 (1997)

En cuanto a encontrar ciclos de longitud impar, es tal y como dice David Eppstein: no se sabe nada mejor que $O(M(n))$ incluido el caso en que $k=3$ .

Sin embargo, si desea detectar caminos de longitud $k$ en lugar de ciclos, puede obtener $O(m+n)$ tiempo, donde $m$ es el número de aristas. No estoy seguro de si el documento original de codificación por colores puede proporcionar este límite de tiempo, pero sí sé que el siguiente documento de algún empollón que se cita a sí mismo al azar lo consigue:

Ryan Williams: Finding paths of length k in O*(2^k) time. Inf. Process. Lett. 109(6): 315-318 (2009)

Answer 2

Si existe un algoritmo determinista o aleatorio con mejor dependencia de $n$ que $M(n)$ incluso para el primer caso no trivial, $k=3$ (es decir, comprobar si el gráfico dado contiene un triángulo) entonces no lo sé. No hay nada mejor en el artículo de Wikipedia sobre grafos sin triángulos por ejemplo. Sin embargo, existen algoritmos cuánticos más rápidos para encontrar 3 ciclos: véase arXiv:quant-ph/0310134 .

También es posible encontrar límites mejores que $M(n)$ para grafos no densos (número de aristas suficientemente inferior al cuadrático). Por ejemplo, incluso algoritmos bastante ingenuos pueden encontrar triángulos en tiempo $O(m^{3/2})$ donde $m$ es el número de aristas del grafo.

Answer 3

Si nos restringimos a la clase de grafos planares, entonces existe un algoritmo de tiempo lineal debido a Eppstein . También es lineal para grafos de anchura de árbol acotada, ya que el problema de encontrar un ciclo de longitud fija puede codificarse fácilmente como una fórmula lógica monádica de segundo orden, y entonces podemos apelar al teorema de Courcelle.

Edita. El problema relacionado de encontrar un ciclo de longitud $a$ (mod $k$ ) no se ha demostrado que sea polinómica (excepto en el caso $a=0$ ).

Answer 4

Básicamente, todos los anteriores han dado en el clavo. Quiero añadir un algoritmo de conteo de todos los ciclos de longitud 4 en un grafo no dirigido, que se ejecuta en $O(n^3)$ en lugar de $O(n^4)$

Cada ciclo de longitud cuatro incluye cuatro nodos $a$ , $b$ , $c$ y $d$ . Así, para cada par de nodos $u$ y $v$ se cuenta el número de nodos que son vecinos tanto de $u$ y $v$ . Entonces el problema de contar cada ciclo de longitud cuatro se transforma en el problema de seleccionar 2 nodos de este tipo que sean adyacentes a ambos $u$ y $v$ .