# Counting number of 1-hop paths in a sparse graph

Given a sparse undirected graph $$G=(V,E)$$ where $$|E|=O(|V|)$$, a one-hop path between a pair of vertices $$(u,v)$$ is a path in $$G$$ connecting $$(u,v)$$ where there is exactly one intermediate vertex between the vertices i.e. $$u \leftrightarrow t \leftrightarrow v$$ where $$t$$ is the intermediate vertex, $$(u,t,v)$$ are distinct vertices.

(actually I am not entire sure if 'one-hop' is the right terminology here. Let's assume it is).

I have $$Q$$ queries, where each query consists of a pair of vertices $$(u,v)$$ in $$G$$ and asks the question: how many distinct one-hop paths exist between the given pair of vertices. For this question let's assume $$Q=O(|V|)$$. All $$Q$$ queries are provided up-front and you do not have to answer the queries in the order given.

While I can solve this problem by counting the paths one by one for each query using an adjacency list, time complexity is $$O(|V|^2)$$. Is there a more efficient way to solve this?

PS: not a home work problem. Just something I have in mind.

• In your analysis, is the $O(|V|^2)$ the running-time per query or is it the entire query? Maybe you want to include the details of your proposed solution. Nov 24, 2022 at 8:16

I think this is possible in $$\mathcal{O}(|V|\sqrt{|V|})$$ for all $$Q$$ queries.

Assume the graph is represented as an array of adjacency sets: for $$v\in V$$, $$G[v]$$ is a set containing all neighbors of $$v$$.

Then the number of $$1$$-hops from $$u$$ to $$v$$ is the size of $$G[v]\cap G[u]$$. This can be computed in $$\mathcal{O}(\min(\deg v, \deg u))$$.

Now the problem is that if the $$Q$$ queries consists of the same query $$(u, v)$$, and it happens that $$\deg u$$ and $$\deg v$$ are $$\mathcal{O}(|V|)$$, that would result in total complexity $$\mathcal{O}(Q|V|) = \mathcal{O}(|V|^2)$$. To avoid that, you can create a hashtable, and each time you make a query, you can add the association $$((u, v), n)$$ to the hashtable. That way, the next time you have to make an already made query, its complexity would be $$\mathcal{O}(1)$$.

Now what is the worst that could happen? If you consider $$V = \{v_1, …, v_n\}$$ with $$\deg(v_1)\geqslant \deg(v_2) \geqslant … \geqslant \deg(v_n)$$, the worst is that the queries would be $$(v_1, v_2)$$, $$(v_1, v_3)$$, $$(v_2, v_3)$$, …

If $$Q \leqslant c|V|$$, that would result is a complexity less than $$\sum\limits_{j=2}^{\sqrt{2c|V|}}\sum\limits_{i=1}^{j-1}\deg(v_j) = \sum\limits_{j=2}^{\sqrt{2c|V|}}(j-1)\deg(v_j)\leqslant \sqrt{2c|V|}\sum\limits_{j=2}^{\sqrt{2c|V|}}\deg(v_j) = \mathcal{O}(|V|\sqrt{|V|})$$ The last equality holds true because $$\sum\limits_{v\in V}\deg(v) = 2|E| = \mathcal{O}(|V|)$$.

Note that in this worst case, we considered an adversarial strategy. Since the average degree of any vertex is $$\mathcal{O}(1)$$, the average complexity would actualy be $$\mathcal{O}(|V|)$$ for all $$Q$$ queries.

• Note that I promised $\mathcal{O}(|V|\sqrt{|V|})$ worst case, but this is not exactly true, because sets and hashtable do not have $\mathcal{O}(1)$ worst case. However, the $\mathcal{O}(|V|)$ average case I talked about still holds. Nov 24, 2022 at 13:34