In the adjacency list model, a graph is described through lists that contain the neighbors of any node $i \in [n]$. A query is of the form "What is the $k$-th neighbor of node $i$?". BFS allows to decide whether the graph is connected in this model in $O(m+n)$ queries, with $m$ the number of edges.

If the lists are unordered then this is tight, see e.g. [1] for a $\Omega(m+n)$ lower bound. What is the query complexity if the lists are ordered?

Background: my question comes from looking at Laplacian solvers for graph problems. Here sparse matrix access is given of the form "What is the $k$-th nonzero element of the $i$-th row?", which corresponds to an ordered adjacency list.

Some Intuition: at least in some cases the ordered list model is stronger than the unordered list model. Let $G$ be two separate cliques on nodes $[1:n/2]$ and $[n/2+1:n]$, and $G'$ the same graph in which we change edges $(i,j)$ and $(i',j')$ from separate cliques into edges $(i,i')$ and $(j,j')$. Then by a sensitivity argument this requires $\Omega(n^2)$ queries in the unordered list model. In the ordered list model we can do this in $n/2$ queries: for every node $i\in[1:n/2]$, check whether it has a neighbor in $[n/2+1:n]$ (this requires a single query).

[1] Eden and Rosenbaum. "Lower Bounds for Approximating Graph Parameters via Communication Complexity." APPROX/RANDOM 2018.


Your Answer

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

Browse other questions tagged or ask your own question.