Graph adjacency using Hashing

Question

Consider a graph $G = (V,E)$ and the following operation

$\text{neighbour}(v_1,v_2)$: returns true if the vertices $v_1$ and $v_2$ are adjacent, and false otherwise.

I now consider two standard data structures:

Adjacency Matrix. Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.

Adjacency List. Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.

My question is the following:

How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)

Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?

Answer 1

With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.

Answer 2

I have done it this way, but this implies you have your nodes represented as integers from $0$ to $|V| - 1$. It is actually quite similar to adjacency lists, but instead of have a list to store the indexes of the neighbors you will have a hash table (or a hash set depending on your specific problem), the space complexity depends on the specific implementation but with a dynamic array tou may reach $O(|d_{i}|)$ for a given node $i$, to achieve a $O(|E|+|V|)$ space complexity.

In terms of time, as you have a list of hash tables/sets the access for a given node is constant in the list, and depending on your hashing scheme you may achieve $O(1)$ access for each node. As I've mentioned before this assumes you have represented your nodes as integers, so a common hashing method as Knuth's multiplicative method would be fine to retain constant access.

Another option is to represent your graph directly as edges and do a hashing function over the pairs of nodes that represent an edge, this would lead to $O(|E|)$ in theory, depending on your implementation. A common way to implement those hash function is to combine the hash functions of each component of the pair, typically computing the xor of the hash functions. If you already know the size of the graph and it is static is straightforward to came up with a perfect hash function to achieve a tight bound in space and complete $O(1)$ access. It depends on the problem you are solving though.