5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Your definition of $P_{i,j}$ seems incomplete. Consider the pre-order $P := \{(1,2),(2,3),(3,4),(4,5)\}$, i.e. in which $1 < 2 < 3 < 4 < 5$. What is $P_{1,5}$? Or do you intend $P_{i,j}$ to be defined only for pairs $i \leqslant j$ for which $\forall k: \Bigl((i \leqslant k) \implies (j \leqslant k)\Bigr) \;\&\; \Bigl((k \leqslant j) \implies (k \leqslant i)\Bigr)$? $\endgroup$ – Niel de Beaudrap Mar 23 '13 at 14:04
  • $\begingroup$ Indeed it is only defined for those $k$. I edited the question. Thank you $\endgroup$ – Arthur MILCHIOR Mar 23 '13 at 20:04
  • $\begingroup$ Is the total pre-order problem at the end the one you care more about? If you're actually given a particular total pre-order, that may be easier. (I'll think about the more general problem.) $\endgroup$ – Niel de Beaudrap Mar 24 '13 at 1:26
  • $\begingroup$ To be more precise, what I really care about is a more complicated structure that may state $i<j$, $i=j$, $i!=j$ or $i<=j$, but I assumed that pre order would be a good first step. Thank you a lot. $\endgroup$ – Arthur MILCHIOR Mar 24 '13 at 5:33
  • $\begingroup$ Please elaborate — do you mean a data structure which represents not only a pre-order by describing relationships which actually obtain, but also describes invalid ways of extending the order by describing relations which "definitely do not obtain"? $\endgroup$ – Niel de Beaudrap Mar 24 '13 at 9:47
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you a lot for your detailled anwser. There is still one question I don't know the answer of. If for every total order $T$ it is a superset of a partial order $P∈S$. I will also need to figure out if I can extend this to the more complicated data structure I'm really working on. I.e. order stating $i<j$, $i\le j$, $i=j$, $i\not=j$ or $i$ and $j$ may be whatever. $\endgroup$ – Arthur MILCHIOR Mar 24 '13 at 5:40
  • $\begingroup$ I think I understand: you explicitly meant your remark about partitioning $T_r$, that it is a problem which you would like to efficiently decide. I imagine that this would only happen quite rarely. How large is $S$ typically, and how sparse will its elements be? This problem feels to me like DNF-TAUTOLOGY in that elements of $S$ describe sufficient conditions for a total order to extend it, and you would like to know if all total pre-orders fit one of the sufficient conditions. I may elaborate this answer re: pre-orders, and will await to address your other order type once you've clarified. $\endgroup$ – Niel de Beaudrap Mar 24 '13 at 10:08
  • $\begingroup$ I am interested in worst case analysis, so I can not tell that $S$ is going to be small or big. I can imagine case where $|S|$ is $1$, or when it is maximal, i.e. ${r!\over 2\log(2)^{r+1}}$. This question happens only one, at the end of the algorithm, I must accept iff $S$ is indeed a partition of $\mathbb N^r$. But it must be efficient, I can't test every total preorder, that's too long. I'll look at DNF-TAUTOLOGY. Thank you a lot $\endgroup$ – Arthur MILCHIOR Mar 25 '13 at 1:16
  • $\begingroup$ @ArthurMILCHIOR: I have updated my answer, please give it a look. $\endgroup$ – Niel de Beaudrap Mar 30 '13 at 16:30
  • $\begingroup$ I don't understand why you wrote "we forbid either $a \leqslant b$ or $b \leqslant a$ from holding". Since for $a\not=b$ we would have $a< b$ or $b< a$, which implies $a\le b$ or $b\le a$. Apart from that, it seems helpful, thank you a lot $\endgroup$ – Arthur MILCHIOR Mar 31 '13 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.