Compatible partial permutations

Question

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)

Answer 1

We can reduce it to the following problem:

Given a directed graph on vertex set $\{1,2,\dots,n\}$, we want to know if there exists a permutation $T$ such that for each edge $(i,j)$ in the graph, $T[i]<T[j]$.

The reduction: add an edge to the graph for each pair $i,j$ where both $P_b[i]$ and $P_b[j]$ exist for some $b \in \{0,1\}$; the orientation of the edge is determined by whether $P_b[i]<P_b[j]$ or not. This yields a directed graph that contains the union of edges from $P_0$ plus edges from $P_1$.

Conveniently, the new problem is easy. Of course, if there are any cycles in the graph, then there is no such permutation $T$ (i.e., the two permutations $P_0,P_1$ are not compatible). Conversely, if there are no cycles in the graph, then there is such a permutation $T$ (i.e., the permutations $P_0,P_1$ are compatible). Do you see why? We can simply apply a topological sort to the graph and use it to construct an example of such a permutation $T$, where we assign $T[i]=j$ if vertex $i$ is the $j$th vertex to be visited in the topologically sorted order.

I'm not sure what BDDs have to do with it. This does not seem like a research-level question.