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.


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.