Efficient representation of set of partial order

Question

I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.

Let $r$ be an integer, let $P_r$ be the set of partial (pre)order over $[1,r]$ and $T_r$ the set of total (pre)order. I say that $P\in P_r$ is included in $T\in T_r$ if it is included as subset of $[1,r]^2$, or to state it another way, if for all $i,j$ with $i$ less than $j$ for $P$ then it is also less for $T$. Finally I say that $P$ and $P'$ are incompatible if there is $i,j$ with $i<j$ for $P$ and $i>j$ for $P'$ (or if $i=j$ for $P$ and $i<j$ for $P'$).

Let $P\in P_r$ with $i<j$ and no $k$ such that $i<k<j$, then $P_{i,j}$ is the same partial (pre)order, except that $i$ and $j$ are incomparable.

I would like to find an efficient data structure to store a subset of $P_r$. I can't imagine something better than a trie of depth $r(r-1)/2$, with one level for every pair $(i,j)$ with $i<j$. If possible I would want to be able to efficiently add and remove elements from the set, or at least to easily transform $P$ into $P_{i,j}$ as defined above.

I need to know if for a given subset $S$ of $P_r$ and $P\in P_r$, $P$ is incompatible with every $P'\in S$. Or an equivalent problem would be to figure out if a set $S$ is such that its element are one to one incomparable. I also need to know if for every total (pre)order $T$ it is a superset of a partial order $P\in S$.

Intuitively, to each $P\in P_r$ is associate its set $T_P=\{T\in T_r\mid T\supseteq P\}$ and I need to know if $(T_P)_{P\in S}$ form a partition of $T_r$. Then let $T_S=\bigcup_{P\in S} T_P$, then I would also be interested by having a way to efficiently describe $T_S$. (That is, efficiently checking for a given $T\in T_r$ if $T\in T_S$.

---

Finally, I will introduce the real structure I'm interested in, which is more complicated and probably less usual.

A partial preorder $P$ can be seen as partial function from $[1,r]^2$ to $\{<,>,=\}$, where $i=_P j$ if $i<j$ and $j<i$ in $P$ and $f(i,j)$ is undefined if neither $i<j$ nor $i>j$ in $P$. We can associate to $P$ a subset of $\mathbb N^r$ called $\mathbb N_P$ defined by $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$ $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$.

The real data structure I must study is the structure of partial function from $[1,r]^2$ to $\{<,\le,>,\ge,=,\not=\}$. I will call this structure "extended preorder". Let $P$ be an extended preorder, where $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$ $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$, for all $i\le j$, $x_i\le x_j$, and for all $i\not_P=j$, $x_i\not=x_j$.

I say that a total preorder $T$ is included in an extended preorder $P$ if $i\le_Pj$ implies $i<_Tj$ or $i=_Tj$, and $i\not=_Pj$ imply $i<_Tj$ or $j<_Ti$.

The operation I must have are still the same, having a set $S$ of extended preorder, verify if an extended preorder is incompatible with every extended preorder of the set, and verify that every total preorder is included in an extended preorder of the set. Or to say it another way, $(\mathbb N_P)_{P\in S}$ is a partition of $\mathbb N^r$.

Answer 1

Restrictions on pre-orders

You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order with a list of forbidden relationships: that is, we specify $a < b$ using a pre-order which specifies $a \leqslant b$ along with many other relationships, and by separately specifying that $b \leqslant a$ is forbidden.

We may similarly represent $a \not\cong b$ by having any pre-order in which at least one of $a \leqslant b$ or $b \leqslant a$ fails to hold. (I got this confused in a previous edit.)

So: we will consider how to represent pre-orders, and presume that we have a list of further restrictions representing relations of the type $\leqslant$, $\geqslant$, and $\cong$ which we forbid between certain pairs. (For each pair $(a,b)$, there are then four possibilities for forbidden relations, including the the case of no forbidden relation.) The forbidden relations I would represent as a list, which we will later iterate through exactly once; however, in order to be able easily to remove restrictions when computing the order $P_{a,b}$ from a pre-order $P$, you might want to combine this list structure with an $r \times r$ array $F$ which stores for each $1 \leqslant a < b \leqslant r$ what sort of relation (if any) is forbidden between $a$ and $b$.

Representing pre-orders

You can easily represent a partial order by a transitive reduction: a minimal relation (naturally represented as a directed graph, via adjacency lists for immediate predecessors and immediate successors) subject to the constraint of having the partial order as its transitive closure. For a pre-order, you can instead use a relation $R$ which would be the transitive reduction if you "collapsed" all sets of equivalent elements to a single item each; where for all $i \leqslant j$, we have $(i,j) \in R$ if and only if $\exists k: i \leqslant k \leqslant j$ implies that $j \leqslant i$. That is, $(i,j) \in R$ only if one of the following holds:

• $i < j$ and $\neg\exists k: i < k < j$;

• $i \leqslant j$ and $j \leqslant i$.

Such a relation can be easily computed by reduction to computing the transitive reduction of the partial order obtained, as I described, by collapsing equivalence classes (using only one representative node for each equivalence class, and then copying relations across the class). This can be done in time $O(r^3)$ or better.

Given such a representation of pre-orders $P$ by reductions $R$, one may decide $(i,j) \in P$ by testing $(i,j)$-connectivity in $R$, e.g. by breadth-first search. This, of course, takes time $O(n)$. However, one can quite efficiently compute the reduction $R_{i,j}$ of the pre-order $P_{i,j}$ for $i<j$, by

1. copying the immediate successors of $j$ and sharing them with $i$,
2. copying the immediate predecessors of $i$ and sharing them with $j$,
3. removing the relation $(i,j)$ from $R$.

The complexity of this is essentially the sum of the in-degree of $i$ and the out-degree of $j$. I imagine that you would also like to remove the prohibition on $i \leqslant j$ and/or $j \leqslant i$ at the same time; we can achieve this simply by removing any restrictions which are stored at $F[i,j]$ or $F[j,i]$ as appropriate.

Representing subsets of $S \subseteq P_r$

Assuming that all you want to use the subsets $S \subseteq P_r$ for is to check compatibility of individual pre-orders with the elements of $S$, I think the best approach is to store an $r \times r$ array where each element $(i,j)$ contains a collection which indicates the labels of all pre-orders $P \in S$ such that $(i,j) \in P$. (That is: you do not need to store any forbidden relationships.)

The collection may as well be a simple list, for small sets $S$ or if the orders which it contains don't have too many common relations (e.g. minimal and maximal elements in common); otherwise use your set-implementation of choice (e.g. balanced search trees) instead. This can be updated simply by adding a new relation $P'$ to the entries for all pairs $(i,j)$ which are contained in $P'$. If $P'$ is represented by a reduction $R'$, one may do this by a depth-first search from its minimal elements (which one may store a list of in the representation), and performing depth-first search to find all descendants of each element.

• If one maintains a list of traversed nodes along each path of the traversal, one may add each newly traversed node to the descendants of each of those already on the list; after finishing a traversal, pop the node off the list and mark it as visited.

• For each visited node, we copy its descendants to any nodes on the traversal-list, rather than re-traversing it.

This is also a good thing to do, to compute a more explicit representation of $P'$ from $R'$, once your interest in $P'$ becomes dominated by testing $(i,j) \mathbin{\in?} P'$. This will take time $O(r^2)$, as there is essentially unit cost to reverse each edge $(i,j) \in R$, and to record each of the descendants of any $i \in [1,r]$ throughout the traversal. If $s = |S|$ and you use trees for collections at each index $(i,j)$, constructing the representation for $S$ takes time $O(r^2 s \log s)$, with the $\log s$ factor being saturated in the case where many elements of $S$ share many pairs $(i,j)$ in common. This works best for partial orders which are sparse and essentially unrelated, which would reduce both the expected overlap for pairs $(i,j)$ and the number of entries $(i,j)$ for which any relationship is recorded in the traversal of its reduction.

Having this representation of $S$, you can test incompatibility of $P$ with $S$ (where $P$ is given by a reduction $R$) as follows.

1. Initialise a list of all of the elements of $S$, representing those which are potentially compatible with $P$.

2. Iterate through your forbidden relations, and remove from the list of potentially compatible relations, any element of $S$ which violates any of the constraints. (That is, if $a \leqslant b$ is forbidden, remove any element of $S$ for which that relation holds; and similarly for any element of $S$ fo which $a \cong b$, if that relation is forbidden.)

3. Perform a breadth-first search of $R$: and at each link $(i,j) \in R$ traversed, remove from the list of potentially-compatible orders any order $P$ for which $j < i$, by checking for each order on the list whether this is the case.

If the list of potentially-compatible orders ever becomes empty, then $P$ is incompatible with $S$. Otherwise, the list contains at least one partial order in $S$ with which $P$ is compatible.

We can bound each index search $(i,j)$ for a potentially-compatible order by $O(\log s)$, for $s =|S|$; this will happen for each "reduced" relation in $P$, that is for every ordered pair in $R$. If $m = |R|$, then the worst case is $O(ms \log s) \subseteq O(r^2 s \log s)$, in the case that every element of $S$ is compatible with $P$. If you have $f = |F|$ forbidden relationships, then iterating through these and eliminating potentially compatible relations takes time $O(f \log s)$; this is also dominated by $O(r^2 \log s)$, though the larger $f$ is the faster the subsequent compatibility-checking becomes.