Algoritmo para encontrar todas as listas de vizinhos de 2 hop em um gráfico

Dado um gráfico , onde . O que é um algoritmo rápido para gerar o conjunto de todas as listas de vizinhança 2-hop de todos os nós em . $G = (V,E)$ $|V| = n$ $V$

Ingenuamente, você pode fazer isso em . Com o poder das matrizes, você pode fazer isso com usando o algoritmo Strassen. Você pode fazer melhor que isso usando outro algoritmo de multiplicação de matrizes. Algum método melhor? Algum algoritmo de Las Vegas? $O(n^3)$ $O(n^{2.8})$

algorithms algorithm-analysis graphs randomized-algorithms AJed
fonte

Existe um algoritmo determinístico O (n ^ 2).

Mike G

@MikeG como fazer isso?

AJed

@MikeG encontrou um algoritmo maravilhosa quadrática matriz do tempo de multiplicação que infelizmente é muito pequeno para caber dentro de um comentário Stackexchange

Sasho Nikolov

@SashoNikolov Você pode dar uma referência?

Raphael

Respostas:

A questão realmente depende de qual é a definição precisa de um 2-hop. Se por um salto de 2 segundos você quer dizer o conjunto a resposta atual é não, você não pode fazê-lo mais rapidamente que que é a constante usual associada à complexidade de executar o produto da matriz.

h p (v) = {você ∣ existe um caminho de comprimento 2 entre uev},

$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$

O (n^{ω})

$O(n^{\omega})$

ω

$\omega$

Por quê? Para cada vértice verifique se é adjacente ao vértice emSe for esse o caso, você encontrou um triângulo no seu gráfico. Além disso, o gráfico é livre de triângulo se você não encontrar um vértice com essa propriedade. $v$ $v$ $hp(v).$ $v$

O algoritmo atualmente mais conhecido para testar se um gráfico está livre de triângulos possui complexidade de tempo $O(n^{\omega}).$

Jernej
fonte

Interessante, você tem uma referência para o problema de reconhecimento sem triângulo. Existe um limite inferior comprovado para esse problema?

precisa saber é

Não, não há limite inferior comprovado, mas recentemente, foi encontrada uma conexão muito surpreendente. Se você conseguir detectar triângulos mais rapidamente do que

O (n^{ω})

$O(n^{\omega})$ então você pode calcular o produto da matriz mais rapidamente do que

O (n^{ω})

$O(n^{\omega})$ . Veja o artigo "Detecção de triângulo versus multiplicação de matrizes: um estudo da redutibilidade verdadeiramente subcúbica" de Williams e Williams. Aqui kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Jernej

Limpo, feliz que ajudou!

Jernej