Reachability in Dynamic Line Graph

Question

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely

• $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position immediately after $v_j$; that is, after calling this function, the graph $G$ becomes (if $i > j$) $$ v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_j \rightarrow v_i \rightarrow v_{j+1} \rightarrow \cdots \rightarrow v_{i-1} \rightarrow v_{i+1} \rightarrow \cdots $$

• $\mathsf{reachable}(v_i, v_j)$: whether $v_j$ is reachable from $v_i$ in $G$; that is, whether there is a path from $v_i$ to $v_j$

My current idea is to arrange $v_1$, $v_2$, $\cdots$, $v_n$ in a balanced binary tree such that if $v_j$ is reachable from $v_i$, then either one of below holds:

• $v_j$ is in the right subtree of $v_i$;

• $v_i$ is in the left subtree of $v_j$;

• there is a node $v_k$ such that $v_i$ is in the left subtree of $v_k$ and $v_j$ is in the right subtree of $v_k$.

Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another. Therefore, two operations above can be implemented in $O(\log n)$ time.

Q: Is there a better data structure with better complexity please?

Answer 1

Nomenclature aside (a line graph is something different than what you describe), you appear to be describing the problem of ''maintaining order in a list''. You have a list of items $v_i$ (your graph), you can remove an item from one point in the list and re-insert it elsewhere, and you want to check whether one item appears earlier than another in the list. This problem has a constant-time solution; see Dietz and Sleator, "Two algorithms for maintaining order in a list", STOC 1987, https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html and https://en.wikipedia.org/wiki/Order-maintenance_problem