Algoritmo per trovare tutti i vicini liste 2-hop in un grafico

Question

Dato un grafo $ G = (V, E) $, dove $ | V | = N $. Che cosa è un algoritmo veloce per generare la raccolta di tutte le liste di quartiere 2-hop di tutti i nodi di $ V $.

Ingenuamente, si può fare in $ O (n ^ 3) $. Con una potenza di matrici, si può fare con $ O (n ^ {2,8}) $ utilizzando l'algoritmo Strassen. È possibile fare meglio di questo utilizzando un altro algoritmo di moltiplicazione di matrici. Qualsiasi metodo migliore? Qualsiasi algoritmo di Las Vegas?

Answer 1

La domanda in realtà dipende da ciò che è la definizione precisa di un 2-hop. Se da un-hop 2 si intende l'insieme $$ CV (v) = \ {u \ metà \ mbox {v'è un percorso di lunghezza 2 uave} \}, $$ allora la risposta attuale non è, si non può farlo più velocemente di $ O (n ^ {\ omega}) $, dove $ \ omega $ è il solito costante associata con la complessità di eseguire il prodotto di matrice.

Perché? Per ogni vertice $ v $ di controllo se $ v $ è adiacente al vertice in $ CV (v). $ Se questo è il caso allora avete trovato un triangolo nel grafico. Inoltre il grafico è triangolo gratuito se non si trova un vertice $ v $ con questa proprietà.

L'algoritmo attualmente più noto per la prova, se un grafico è privo di triangolo ha complessità temporale $ O (n ^ {\ omega}). $