Counting number of 1-hop paths in a sparse graph

Question

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.

Answer 1

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.