# Connectivity with ordered adjacency list

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.  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).

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