<h2>Restrictions on pre-orders</h2>

<p>You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a &lt; 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 &lt; b$ using a pre-order which specifies $a \leqslant b$ along with many other relationships, and by separately specifying that $b \leqslant a$ is <em>forbidden</em>.</p>

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

<p>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 <em>no</em> 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 &lt; b \leqslant r$ what sort of relation (if any) is forbidden between $a$ and $b$.</p>

<h2>Representing pre-orders</h2>

<p>You can easily represent a partial order by a <a href="http://en.wikipedia.org/wiki/Transitive_reduction" rel="nofollow">transitive reduction</a>: 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:</p>

<ul>
<li><p>$i &lt; j$ and $\neg\exists k: i &lt; k &lt; j$;</p></li>
<li><p>$i \leqslant j$ and $j \leqslant i$.</p></li>
</ul>

<p>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 <a href="http://en.wikipedia.org/wiki/Transitive_reduction#Computational_complexity" rel="nofollow">$O(r^3)$ or better</a>.</p>

<p>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&lt;j$, by</p>

<ol>
<li>copying the immediate successors of $j$ and sharing them with $i$,</li>
<li>copying the immediate predecessors of $i$ and sharing them with $j$,</li>
<li>removing the relation $(i,j)$ from $R$.</li>
</ol>

<p>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.</p>

<h2>Representing subsets of $S \subseteq P_r$</h2>

<p><em>Assuming</em> 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.)</p>

<p>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.</p>

<ul>
<li><p>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.</p></li>
<li><p>For each visited node, we copy its descendants to any nodes on the traversal-list, rather than re-traversing it.</p></li>
</ul>

<p>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.</p>

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

<ol>
<li><p>Initialise a list of all of the elements of $S$, representing those which are potentially compatible with $P$.</p></li>
<li><p>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.)</p></li>
<li><p>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 &lt; i$, by checking for each order on the list whether this is the case.</p></li>
</ol>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-24T05:40:37.467Z
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.
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-24T10:08:26.197Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-25T01:16:18.750Z
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
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-30T16:30:01.020Z
@ArthurMILCHIOR: I have updated my answer, please give it a look.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-31T08:57:51.823Z
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
Arthur MILCHIOR
CC BY-SA 3.0
2013-04-01T13:48:38.130Z
@ArthurMILCHIOR: I knew that there was something of my treatment of that case which seemed different from how I first thought of it. It's fixed now, does this seem better?
Niel de Beaudrap
CC BY-SA 3.0
2013-03-24T03:31:16.817Z
2013-04-01T13:47:58.300Z
2013-04-01T13:47:58.300Z
Niel de Beaudrap
<p>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.</p>

<p>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&lt;j$ for $P$ and $i&gt;j$ for $P'$ (or if $i=j$ for $P$  and $i&lt;j$ for $P'$).</p>

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

<p>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&lt;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.</p>

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

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

<hr>

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

<p>A partial preorder $P$ can be seen as partial function from $[1,r]^2$ to $\{&lt;,&gt;,=\}$, where $i=_P j$  if $i&lt;j$ and $j&lt;i$ in $P$ and $f(i,j)$ is undefined if neither $i&lt;j$ nor $i&gt;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&lt;_Pj$  $x_i&lt;x_j$ and for all $i=_Pj$, $x_i=x_j$.</p>

<p>The real data structure I must study is the structure of partial function from $[1,r]^2$ to $\{&lt;,\le,&gt;,\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&lt;_Pj$  $x_i&lt;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$.</p>

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

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

CC BY-SA 3.0
2013-03-23T14:04:26.497Z
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)$?
Niel de Beaudrap
CC BY-SA 3.0
2013-03-23T20:04:37.307Z
Indeed it is only defined for those $k$. I edited the question. 
Thank you
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-24T01:26:24.693Z
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.)
Niel de Beaudrap
CC BY-SA 3.0
2013-03-24T05:33:38.693Z
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.
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-24T09:47:32.530Z
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"?
Niel de Beaudrap
CC BY-SA 3.0
2013-03-25T01:08:23.457Z
I extended my question to have a more precise description of the data structure I really need. I guess I may have written this first, but I didn't wanted the question to be too complicated. (And I guess  I may probably be able to extend your answer to my real problem if I take some time to really think about it)
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-25T01:21:07.207Z
An initial approach would be to think of your extended pre-orders as being (almost) a combination of a pre-order $P$ which describes necessary relations, and another relation $F$ which describes a collection of forbidden relations. We may think of $P$ as providing positive relations of the form $i \leqslant j$ and $F$ as providing negative relations of the form $j \not\le i$, to indicate $i < j$. This is very easy to deal with. Constraints $i \not\cong j$ are disjunctions of two such pairings: they can also be treated, but with a bit more work. I will elaborate my answer tomorrow.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-25T04:59:52.907Z
I do not like the idea of describing $P$ as a collection of preorder because if $1\le 2\dots\le r$ then it takes $2^r$ pre-order to describe it, it's too much.
Arthur MILCHIOR
CC BY-SA 3.0
2013-03-25T11:01:09.617Z
True; the "collection" idea is essentially an initial sketch which is meant to suggest how I think my answer may be extended — I wouldn't suggest that as an actual representation, even if there were only one usage of "$\not\cong $", essentially for aesthetic reasons. I will elaborate later.
Niel de Beaudrap
<ds.algorithms><partial-order><order-theory><total-ordering>
Efficient representation of set of partial order
Arthur MILCHIOR
# Efficient representation of set of partial order

(Asked by: username_0 on 2013-03-22)

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 $ij$ for $P'$ (or if $i=j$ for $P$ and $i

Let $P\in P\_r$ with $i

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

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

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

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

**Tags:** ds.algorithms, partial-order, order-theory, total-ordering
> **Comments:**
> **username_1**: 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)$?  
> **username_0**: Indeed it is only defined for those $k$. I edited the question.  Thank you  
> **username_1**: 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.)  
> **username_0**: 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.  
> **username_1**: 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"?  
> **username_0**: I extended my question to have a more precise description of the data structure I really need. I guess I may have written this first, but I didn't wanted the question to be too complicated. (And I guess  I may probably be able to extend your answer to my real problem if I take some time to really think about it)  
> **username_1**: An initial approach would be to think of your extended pre-orders as being (almost) a combination of a pre-order $P$ which describes necessary relations, and another relation $F$ which describes a collection of forbidden relations. We may think of $P$ as providing positive relations of the form $i \leqslant j$ and $F$ as providing negative relations of the form $j \not\le i$, to indicate $i < j$. This is very easy to deal with. Constraints $i \not\cong j$ are disjunctions of two such pairings: they can also be treated, but with a bit more work. I will elaborate my answer tomorrow.  
> **username_0**: I do not like the idea of describing $P$ as a collection of preorder because if $1\le 2\dots\le r$ then it takes $2^r$ pre-order to describe it, it's too much.  
> **username_1**: True; the "collection" idea is essentially an initial sketch which is meant to suggest how I think my answer may be extended — I wouldn't suggest that as an actual representation, even if there were only one usage of "$\not\cong $", essentially for aesthetic reasons. I will elaborate later.  

---

## 1 answers

### Answer by username_1 on 2013-03-24. Score: 7 | Accepted answer

## 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Transitive_reduction#Computational_complexity).

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

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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  
> **username_1**: @ArthurMILCHIOR: I have updated my answer, please give it a look.  
> **username_0**: 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  
> **username_1**: @ArthurMILCHIOR: I knew that there was something of my treatment of that case which seemed different from how I first thought of it. It's fixed now, does this seem better?  

---

