The time complexity of finding a neighborhood graph provided an unordered adjacency matrix

Imagine I have an unordered adjacency matrix for some graph $G$ with a set of vertices $V$ and a set of edges $E$. I would like to find a subset of edges that determines a $k$-hop neighborhood graph about a chosen vertex $v_i \in V$ (i.e. a graph consisting of the vertices and edges "reachable" in $k$ edge-wise hops from $v_i$ and the set of all edges between these vertices that exist in $G$).

We allow any standard data structure for $G$. Can I achieve a linear or near-linear time complexity for returning an adjacency matrix for this neighborhood graph as a function of the number of vertices in the neighborhood graph $||V_{neighborhood}||$? What is the best known algorithm for finding these neighborhood graphs?

What if we know something about the structure of the graph, perhaps that we're on a rectangular or hexagonal lattice?

• You could use Dijkstra's algorithm to solve the shortest path problem from $v_i$ and then pick those vertices with path length at most $k$. Complexity will be $O(|E|+|V|\log |V|)$ – polkjh Feb 12 '13 at 12:56
• @polkjh That should work, so a "yes" for the "almost linear time". – R.H. Feb 12 '13 at 13:10
• Is $v_i$ fixed? Or you want these $k$-hop neighbourhoods for all vertices? – Paresh Feb 12 '13 at 13:11
• If it is fixed, you can do it in linear time. – Paresh Feb 12 '13 at 13:11
• @Paresh Thanks - Do you know if the linear time algorithm has a name? And if we want them for all vertices, can we do better than to repeatedly apply the linear time algorithm for a single vertex? – R.H. Feb 12 '13 at 13:13

You can do a simple Breadth First Search from the start node. It starts with the first node, and adds all its neighbours to a queue. Then, it de-queues each node, finds its unvisited neighbors to the queue and marks the current node visited. The key observation here is that the all the vertices that are at some distance $d$ from the start vertex, are in one contiguous block in the FIFO queue. If you can keep track of how deep you are in the queue, you can stop after $k$-levels. More specifically, the moment you de-queue a vertex that you know is at a distance of $k$ from the start node, you don't have to enqueue any more, just go on till the queue is empty, and you are done. Using BFS in this way will give you vertices in increasing order of hops/distance from the start.

You can also adapt the Depth First Search algorithm for this, by limiting the depth to $k$. This is easier to code, but won't give vertices in order of distances from the start. So, for some of the discovered vertices, you may later find a shorter path. But no vertex will have to be discarded after being discovered in either methods.

Both these algorithms are linear in the size of the graph - $O(|V|+ |E|)$ even if they traverse the whole graph. But since you are stopping much sooner, they would be very efficient. More specifically, they will visit only those edges and vertices that are actually in the $k$-hop neighborhood, and nothing more -- $O(|V_s|+|E_s|)$, where $V_s$ and $E_s$ are the number of vertices and edges in the $k$-neighborhood subgraph. Another consideration can be that if $k$ is small but vertex degrees are very large, you might prefer DFS.

k-hops for all vertices:
If the graph is sparse, that is, $|E| = O(|V|)$, then running a BFS/DFS from each node should be the best option asymptotically. Rectangular or hexagonal lattice graphs are sparse graphs. So, complexity would be $O(|V|^2)$. I do not think that there should be anything asymptotically faster than this for sparse graphs, though there may be other solutions that are more efficient (but still quadratic).

If the graph is not sparse, you can compute the $k$-th power of the adjacency matrix in $O(n^{\omega}\log k)$ time, where $\omega$ is the constant of matrix multiplication. The current best known algorithm has $\omega = 2.3727$. But in practice, the simple cubic matrix multiplication ($\omega = 3$) is the most efficient. You could also use the all-pair shortest path algorithm by Floyd-Warshall and find those vertices that have distance atmost $k$. This is $O(|V|^3)$

• Wouldn't we expect that the time for find each subgraph with a BFS or DFS with bounded depth $k$, would be $O(||E_s||+||V_s||)$ where $E_s$ and $E_s$ are the ultimate number of edges and vertices in the subgraph (and not the full graph, $G$)? – R.H. Feb 12 '13 at 15:48
• You are right. This is exactly what I meant when I said "More specifically, they will visit only those edges and vertices that are actually in the k-hop neighborhood, and nothing more." I'll add your description to this line as it is more formal. – Paresh Feb 12 '13 at 15:53
• Thus, our final time complexity for computing the $k$-hop subgraphs for all vertices would be $\approx O(||V_G||)$ for fixed $k$, right? – R.H. Feb 12 '13 at 15:54
• I think this is a bit more involved. In the graphs you mention - rectangular or hexagonal lattices - the time complexity would indeed be $O(|V_G|)$. However, for general graphs, it could be quadratic - it will depend on the degree distribution of the graphs and maybe other things. The same edges/vertices may be visited multiple times when running BFS/DFS from different vertices. – Paresh Feb 12 '13 at 19:18