Come trovare un triangolo all'interno di un grafico?

Question

Ecco un esercizio nel numero Algorithm Design Manual.

consideri il problema di determinare se un grafo orientato G = (V, E) contiene un triangolo o ciclo di lunghezza 3.

(a) Fornire un O (| V |^3) per trovare un triangolo se ne esiste uno.

(b) Migliora l'algoritmo per l'esecuzione nel tempo O (| V | · | E |). Puoi assumere | V | ≤ | E |.

Si osservi che questi limiti ti dà il tempo per la conversione tra i adiacenza matrice e lista di adiacenza rappresentazioni di G.

Ecco il mio pensiero:

(a) Se il grafico è dato come un elenco di adiacenza, posso convertire l'elenco in matrice con O (| V |^2). quindi faccio:

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; 

Questo dovrebbe dare un O (| V |^3) per testare il triangolo.

(b) Il mio primo intuitivo è che se il grafico viene fornito come elenco di adiacenza, allora farò un bfs. Ogni volta che viene trovato un bordo incrociato, ad esempio, if y-x is a cross edge, allora lo sarà check whether parent[y] == parent[x], if true, then a triangle is found.

Qualcuno potrebbe dirmi se il mio modo di pensare è corretto o no?

Anche per questo (b), non sono sicuro della sua complessità. Dovrebbe essere O (| V | + | E |), giusto?

Come posso farlo in O (| V | * | E |)?

Answer 1

Una possibile soluzione O(|V||E|), è la stessa idea della forza bruta in (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 

controllo tutti i bordi e non tutti i vertici coppie - con un altro vertice che forma un triangolo: sono sufficienti informazioni per determinare se il bordo e il vertice formano una soluzione fattibile.

contatore esempio di soluzione BFS:

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

noti che father[F] != father[G] != father[H], quindi l'algoritmo restituirà false - ma comunque, (F, G, H) è una soluzione praticabile!

Answer 2

Ecco cosa penso:

La soluzione origianl BFS è corretto come indicato sopra. Ma possiamo modificare il DFS. Assegna numeri ai nodi visitati mentre visitiamo ciascun vertice nel DFS. Ora, se raggiungiamo un vertice (nella domanda ho visto i bordi incrociati, non ce ne sono in un grafo non orientato), controlliamo la sua lista di adiacenza e supponiamo che un vertice sia scoperto (ma non elaborato, non può accadere), quindi controlliamo il suo numero . Se la differenza è 2 allora c'è un ciclo di lunghezza 3.

Answer 3

Mi piace molto the matrix multiplication solution discussed in this blog post.

Sia A = matrice di adiacenza

• adiacenze in * una matrice (a2) moltiplicata sono i numeri di percorsi 2-lunghezza
• adiacenze in a2 * una matrice moltiplicata sono i numeri di percorsi 3-lunghezza

Il problema è, moltiplicazione matriciale è lento ... Tuttavia, è possibile utilizzare GPGPU per eseguire la moltiplicazione matriciale e può avere una soluzione performante su architetture moderne che includono una GPU.

Answer 4

Se si dispone di una matrice di adiacenza, è possibile trovare i triangoli quadrando la matrice e verificare se la matrice originale e la matrice quadrata hanno una voce diversa da zero nello stesso punto.

Una moltiplicazione di matrice naive richiede tempo O(n^3), ma esistono algoritmi di moltiplicazione rapida della matrice che funzionano meglio. Uno dei più noti è l'algoritmo Coppersmith-Winograd, che viene eseguito nel tempo O(n^2.4). Ciò significa che l'algoritmo procede in questo modo:

• Utilizzare il tempo O(V^2) per convertire in una matrice di adiacenza.
• Utilizzare il tempo O(V^2.4) per calcolare il quadrato della matrice di adiacenza.
• Utilizzare il tempo O(V^2) per controllare le matrici per le voci diverse da zero coincidenti.
• L'indice della riga e della colonna in cui si trovano le voci diverse da zero coincidenti in (se presenti) indicano due dei nodi coinvolti.
• Utilizzare il tempo O(V) per restringere il terzo nodo comune a entrambi i nodi noti.

Quindi nel complesso ciò richiede O(V^2.4) tempo; più precisamente ci vuole comunque una lunga moltiplicazione della matrice. È possibile passare dinamicamente tra questo algoritmo e l'algoritmo di if-any-edge-end-have-a-common-neighbor that amit explains in their answer per migliorarlo a O(V min(V^1.4, E)).

Ecco uno paper that goes more in-depth into the problem.

È un po 'come le scoperte dipendenti-su-teoriche questo problema è. Se le congetture sulla moltiplicazione di matrici effettivamente quadratiche risultano essere vere, allora si otterrebbe un limite di tempo molto bello di O(V^2) o O(V^2 log(V)) o qualcosa del genere. Ma se i computer quantistici funzioneranno, saremo in grado di fare even better than that (qualcosa come O(V^1.3))!