# Algorithm deciding if a radius of a graph is two

Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?

Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.
• Correct in general, but if the graph is sparse--$|E| \in O(|V|)$--then we do better with BFS. – Ryan Jun 6 '15 at 18:43
• Also BFS has a worst case complexity $O(|V| + |E|)$. – Luke Mathieson Jun 7 '15 at 3:40