Algoritmo para encontrar todas las listas de vecinos de 2 saltos en un gráfico

Dado un gráfico , donde . ¿Qué es un algoritmo rápido para generar la colección de todas las listas de vecindario de 2 saltos de todos los nodos en ? $G = (V,E)$ $|V| = n$ $V$

Ingenuamente, puedes hacer eso en . Con el poder de las matrices, puede hacerlo con utilizando el algoritmo de Strassen. Puede hacerlo mejor que esto usando otro algoritmo de multiplicación de matrices. ¿Algún mejor método? ¿Algún algoritmo de Las Vegas? $O(n^3)$ $O(n^{2.8})$

algorithms algorithm-analysis graphs randomized-algorithms AJed
fuente

Hay un algoritmo determinista O (n ^ 2).

Mike G

@ MikeG cómo hacer eso?

AJed

@MikeG ha encontrado un maravilloso algoritmo de multiplicación de matriz de tiempo cuadrático que desafortunadamente es demasiado pequeño para caber dentro de un comentario de intercambio de pila

Sasho Nikolov

@SashoNikolov ¿Puedes dar una referencia?

Raphael

Respuestas:

La pregunta realmente depende de cuál es la definición precisa de un 2-hop. Si por un 2-hop te refieres al conjunto

h pags (v) = {tu ∣ hay una ruta de longitud 2 entre u y v},

$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$ entonces la respuesta actual es no, no puedes hacerlo más rápido que

O (n^{ω})

$O(n^{\omega})$ dónde

ω

$\omega$ es la constante habitual asociada con la complejidad de realizar el producto matriz.

¿Por qué? Por cada vértice $v$ comprobar si $v$ es adyacente al vértice en $hp(v).$ Si este es el caso, entonces ha encontrado un triángulo en su gráfico. Además, el gráfico no tiene triángulos si no encuentra un vértice $v$ con esta propiedad

El algoritmo más conocido actualmente para probar si un gráfico no tiene triángulos tiene complejidad de tiempo $O(n^{\omega}).$

Jernej
fuente

Interesante, ¿tiene una referencia para el problema de reconocimiento sin triángulos. ¿Existe un límite inferior comprobado para este problema?

AJed

No, no hay límite inferior comprobado, pero recientemente, se encontró una conexión muy sorprendente. Si puedes detectar triángulos más rápido que

O (n^{ω})

$O(n^{\omega})$ entonces puede calcular el producto matricial más rápido que

O (n^{ω})

$O(n^{\omega})$ . Vea el artículo "Detección de triángulos versus multiplicación matricial: un estudio de la reducibilidad verdaderamente subcúbica" por Williams y Williams. Aquí kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Jernej

Genial, me alegro de que haya ayudado.

Jernej