¿Cómo encontrar un triángulo dentro de un gráfico?

Question

Aquí hay un ejercicio en el Algorithm Design Manual.

considerar el problema de determinar si un grafo no dirigido G dado = (V, E) contiene un triángulo o ciclo de longitud 3.

(a) Dar un O (| V |^3) para encontrar un triángulo, si existe.

(b) Mejore su algoritmo para ejecutar en tiempo O (| V | · E |). Puede suponer | V | ≤ | E |.

Obsérvese que estos límites le da tiempo para convertir entre los adyacencia matriz y lista de adyacencia representaciones de G.

Aquí está mi pensamiento:

(a) Si el gráfico se administra como una lista de adyacencia, puedo convertir la lista a matriz por O (| V |^2). entonces lo hago:

for (int i = 0;i < n;i++) 
    for (int j = i+1;j < n;j++) 
    if (matrix[i][j] == 1) 
     for (int k = j+1;k < n;k++) 
     if (matrix[i][k] == 1 && matrix[j][k] == 1) 
      return true; 

Esto debería dar una O (| V |^3) para probar el triángulo.

(b) Mi primera intuición es que si el gráfico se da como una lista de adyacencia, entonces haré un bfs. Siempre que se encuentre un borde transversal, por ejemplo, if y-x is a cross edge, entonces lo haré check whether parent[y] == parent[x], if true, then a triangle is found.

¿Alguien podría decirme si mi pensamiento es correcto o no?

También para esto (b), no estoy seguro de su complejidad. ¿Debería ser O (| V | + | E |), ¿verdad?

¿Cómo puedo hacerlo en O (| V | * | E |)?

Answer 1

Una posible solución O(|V||E|), es la misma idea de la fuerza bruta en (a):

for each edge (u, v): 
    for each vertex w: 
    if (v, w) is an edge and (w, u) is an edge: 
      return true 
return false 

cheque todos los bordes, y no todos los pares de vértices - con otro vértice que forma una triángulo: es información suficiente para determinar si el borde y el vértice forman una solución factible.

Contador ejemplo para solución BFS:

 A 
    /| \ 
    /| \ 
    B C D 
    | | | 
    | | | 
    F---G---H 
    |  | 
    --------- 
    (F, H) is also an edge 

Nota que father[F] != father[G] != father[H], por tanto, el algoritmo regresará falso - pero sin embargo, (F, G, H) es una solución factible!

Answer 2

Esto es lo que pienso:

La solución BFS origianl es incorrecta como se ha señalado anteriormente. Pero podemos modificar el DFS. Asigne números a los nodos visitados cuando visitamos cada vértice en el DFS. Ahora, si alcanzamos un vértice (en la pregunta vi bordes transversales, no hay ninguno en un gráfico no dirigido), verificamos su lista de adyacencia y suponemos que se descubre un vértice (pero no se procesa, no puede suceder), luego verificamos su número . Si la diferencia es 2, entonces hay un ciclo de longitud 3.

Answer 3

Me gusta mucho the matrix multiplication solution discussed in this blog post.

Sea A = la matriz de adyacencia

• Las adyacencias en a * una matriz (a2) multiplicado son los números de caminos 2 de longitud
• Las adyacencias en a2 * una matriz multiplicado son los números de Trayectos de 3 largos

El problema es que la multiplicación de matrices es lenta ... Sin embargo, puede usar GPGPU para realizar la multiplicación de matrices y puede tener una solución de rendimiento en arquitecturas modernas que incluyen una GPU.

Answer 4

Si tiene una matriz de adyacencia, puede encontrar triángulos al cuadrar la matriz y ver si la matriz original y la matriz cuadrada tienen una entrada distinta de cero en el mismo lugar.

Una multiplicación de matriz ingenua lleva tiempo O(n^3), pero hay algoritmos de multiplicación rápida de matrices que funcionan mejor. Uno de los más conocidos es el algoritmo Coppersmith-Winograd, que se ejecuta en O(n^2.4) vez. Eso significa que el algoritmo es algo así como:

• Utilice O(V^2) vez para convertir a una matriz de adyacencia.
• Use O(V^2.4) tiempo para calcular el cuadrado de la matriz de adyacencia.
• Utilice O(V^2) tiempo para verificar las matrices para entradas coincidentes que no sean cero.
• El índice de la fila y la columna en las que se encuentran entradas coincidentes que no son cero en (si corresponde) le informan dos de los nodos implicados.
• Utilice O(V) para reducir el tercer nodo común a ambos nodos conocidos.

De manera general, esto toma O(V^2.4) vez; más precisamente, toma la multiplicación de la matriz por mucho tiempo que tarde. Puede cambiar dinámicamente entre este algoritmo y el algoritmo if-any-edge-end-points-have-a-common-neighbor that amit explains in their answer para mejorarlo a O(V min(V^1.4, E)).

Aquí hay un paper that goes more in-depth into the problem.

Es un poco nítido cuán dependientes son los descubrimientos teóricos de este problema. Si las conjeturas acerca de la multiplicación de matrices en realidad son cuadráticas resultan ser verdaderas, entonces obtendría un límite de tiempo realmente bueno de O(V^2) o O(V^2 log(V)) o algo así. Pero si las computadoras cuánticas funcionan, podremos hacer even better than that (¡algo así como O(V^1.3))!