Encontrar un ciclo de longitud fija

Question

¿Hay algún resultado sobre el tiempo de la complejidad de encontrar un ciclo de longitud fija k en un gráfico general? Todo lo que sé es que Noga Alon et al. el uso de la tecnica se llama "código de color", que tiene un tiempo de ejecución de O(M(n)), donde M(n) es el tiempo de la multiplicación de dos n veces n las matrices.

Hay alguna mejor resultado?

Answer 1

Encontrar un ciclo de cualquiera , incluso de longitud se pueden encontrar en $O(n^2)$ del tiempo, que es menos conocida obligado en $O(M(n))$. Por ejemplo, un ciclo de longitud cuatro se encuentran en $O(n^2)$ momento a través del siguiente procedimiento:

Suponga que el conjunto de vértices es $\{1,...,n\}$. Preparar un $n$ x $n$ matriz $A$ que es principio de todos los ceros. Para todos los vértices $i$ y todos los pares de vértices $j, k$ que son vecinos a $i$, compruebe $A[j,k]$$1$. Si tiene un $1$, la salida de ciclo de cuatro, de lo contrario, establezca $A[j,k]$$1$. Cuando este bucle termina, la salida de ningún ciclo de cuatro.

El algoritmo anterior se ejecuta en la mayoría de los $O(n^2)$ tiempo, ya que para cada triple $i,j,k$ podemos mover de un tirón un $0$$1$$A$, o nos detenemos. (Suponemos que el gráfico está en la lista de adyacencia de la representación, por lo que es fácil para seleccionar pares de vecinos de un vértice.)

El caso general es tratada por Raphy Yuster, y Uri Zwick en el papel:

Rafael Yuster, Uri Zwick: Encontrar Ciclos Incluso Más Rápido. SIAM J. la Matemática Discreta. 10(2): 209-222 (1997)

Como para buscar los ciclos de longitud impar, es igual de David Eppstein dice: no hay nada mejor que se conoce de $O(M(n))$, incluyendo el caso en que $k=3$.

Sin embargo, si usted desea detectar caminos de longitud $k$ en lugar de ciclos, de hecho, puede usted conseguir $O(m+n)$ el tiempo, donde el $m$ es el número de aristas. No estoy seguro de si el original de la codificación de colores de papel puede proporcionar esta limitada en el tiempo, pero sí sé que el siguiente trabajo por algún azar de la auto-citando nerd obtiene:

Ryan Williams: la Búsqueda de caminos de longitud k en S*(2^k) tiempo. Inf. Proceso. Lett. 109(6): 315-318 (2009)

Answer 2

Si hay un deterministas o aleatorios algoritmo con mejor dependencia de la $n$ $M(n)$ incluso para el primer caso no trivial, $k=3$ (es decir, se prueba si el gráfico contiene un triángulo), entonces yo no sé acerca de. Nada mejor aparece en el artículo de la Wikipedia sobre el triángulo libre de gráficos, por ejemplo. Existen algoritmos cuánticos para la búsqueda de 3-ciclos más rápidos, sin embargo: ver arXiv:quant-ph/0310134.

También es posible encontrar los límites que son mejores que los de $M(n)$ para los gráficos que no son densos (número de aristas suficientemente menor que cuadrática). Por ejemplo, incluso bastante ingenuo algoritmos pueden encontrar triángulos en el tiempo $O(m^{3/2})$ donde $m$ es el número de aristas en el grafo.

Answer 3

Si nos restringimos a la clase de los grafos planares, entonces existe un algoritmo de tiempo lineal debido a Eppstein. También es lineal para los gráficos de limitada árbol de ancho desde el problema de encontrar un ciclo de longitud fija, que fácilmente puede ser codificado como un monádico de segundo orden de la fórmula de la lógica, y a continuación, podemos apelar a Courcelle del teorema. Sospecho que la respuesta general de los gráficos es realmente polinomio.

Edit. El problema de la búsqueda de un ciclo de longitud $a$ (mod $k$) no ha sido demostrado ser el polinomio (excepto en el caso de $a=0$).

Answer 4

Básicamente, todo el mundo por encima de dado en el clavo en su cabeza. 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'. por lo tanto para cada par de nodos u y v, se cuenta el número de nodos que son vecinos a ambos u y v. el problema de contar cada ciclo de longitud cuatro se transforma en el problema de la selección de 2 nodos adyacentes de ambos u y v.