Compatible partial permutations

Please, correct my terminology as I am not a combinatorician (I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem.

Let $P_k$ be partial permutations of the set $\{1, 2, \ldots, n\}$, e.g. $n=5$, $P_1=(1,\cdot,3,2,\cdot)$, and $P_2=(\cdot,2,3,1,5)$. Let $T_k$ be permutations from the same set, e.g. $T_1=(1,3,4,2,5)$. I will write $P_1[4]=2$, $P_2[4]=1$, and $T_1[4]=2$. I will say, that $P_1[2]$, $P_1[5]$, and $P_2[1]$ do not exist.

Let define that a given partial permutation $P$ is included in the given permutation $T$ if for all $i,j$ for which $P[i]$ and $P[j]$ exist: if $P[i] < P[j]$ then $T[i] < T[j]$. For example, the given $P_1$ and $P_2$ are both included in the given $T_1$.

Let define that two given partial permutations are compatible if there exists a permutation such that both partial permutations are included in it. For example, the given $P_1$ and $P_2$ are compatible, because they are both included in $T_1$.

QUESTION: Propose an algorithm to check if two given partial permutations are compatible. Please propose also the proper data structure for representing partial orders which will allow your (efficient) algorithm.

(I am tagging this question with BDD because the solution may help me to represent BDDs with different variable ordering more concisely)

Asked by user7015 (223 )
Jan 05, 2014 at 23:37