0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Russel
    Nov 24, 2022 at 8:16

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Nov 24, 2022 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.