Алгоритм, чтобы найти все списки соседей с 2 ​​хопа на графике

Question

Дал график $ g = (v, e) $, где $ | v | = n $. Что является быстрым алгоритмом для создания коллекции всех списков соседей по 2 хопа всех узлов в $ V $.

Наивно, вы можете сделать это в $ O (n^3) $. С силой матриц вы можете сделать это с $ O (n^{2,8}) $ с использованием алгоритма Страсена. Вы можете сделать лучше, чем это, используя другой алгоритм умножения матрицы. Какой -нибудь лучший метод? Любой алгоритм Лас -Вегаса?

Answer 1

Вопрос действительно зависит от точного определения 2-хопа. Если под 2-хоп вы имеете в виду набор $$ hp (v) = {u mid mbox {есть путь длины 2 между u и v} }, $$, тогда текущий ответ-нет, вы не может сделать это быстрее, чем $ o (n^{ omega}) $, где $ omega $ - обычная постоянная, связанная со сложностью выполнения матричного продукта.

Почему? Для каждой вершины $ V $ чек, если $ v $ рядом с вершиной в $ hp (v). $ Если это так, то вы нашли треугольник на своем графике. Более того, график бесплатный треугольник, если вы не найдете вершину $ V $ с этим свойством.

Самый известный в настоящее время алгоритм тестирования, если график не имеет треугольника, обладает временной сложностью $ O (n^{ omega}). $