Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers any query $x\sqsubseteq y$ in constant time.
We define the neighbourhood relation over $\{s_i\}$ as:
For any $\pi=\langle c_i \rangle \in \{s_i\},\tau=\langle c'_i \rangle \in \{s_i\}$, $\pi$ and $\tau$ are neighbours if and only if: (1) $\exists j$, $\neg(c_j\sqsubseteq c'_j)\lor\neg(c'_j\sqsubseteq c_j)$, and (2) $\forall i\neq j, c_i\sqsubseteq c'_i$ or $c'_i\sqsubseteq c_i$. The neighborhood relation is denoted as $\pi \sim \tau$.
An example is taking $=$ as $\sqsubseteq$, then $\pi\sim \tau$ means $\pi$ and $\tau$ have exactly one different item.
Another example is taking a flatten join-semilattice as $D$, then $\pi\sim\tau$ means $\pi$ and $\tau$ has at least one different item and all different item pairs of $\pi$ and $\tau$ contains at least one $\top$ except for one pair.
Now consider the undirected graph $G=(V, E)$, where $v_i \in V$ represent $s_i$, and $(v_i, v_j)\in E$ if and only if $s_i\sim s_j$.
Since for any two sequence $s_i, s_j$, $s_i\sim s_j$ needs $O(m)$ query of $\sqsubseteq$ and $\sqsubseteq$ takes constant time, the complexity of judging $s_i,s_j$ is $O(m)$, and there are $O(n^2)$ pair of $s_i,s_j$, the total complexity is $O(mn^2)$.
Is there an algorithm for computing $G$ with better time complexity?
My initial effort is to consider given three sequence $s_i,s_j,s_k$, there seems does not exist an algorithm taking less than $3\times 2m$ query of $\sqsubseteq$, so the total complexity cannot be less than $O(mn^2)$, but I cannot prove it.
