1
$\begingroup$

Let $S$ be a set of partial preorders over a set $U$ ($\le$ is a preorder/quasiorder if $\forall x,y,z\in U$, $x\le x$ and $x \le y \land y \le z \implies x \le z$). We say that a partial preorder represents a total preorder if the former is contained in the latter [1]. We say that a set of partial preorders covers a total preorder if there exists some partial preorder in the set which represents the total preorder. We say that a set of partial preorders over $U$ is complete if it covers all possible total preorders over $U$.

Examples ($U=\{a,b,c\}$):

  • $a<b$ represents $a<b<c$, $a<c<b$, $c<a<b$, $a<b≤c$, etc.
  • $\{a<b,a<c\}$ covers $a<b<c$, $a<c<b$, $a<c≤b$, etc.
  • $\{a<b,a=b,a>b\}$ is complete over $U$.

The goal is to find if there is a total preorder which is not covered by a set of partial preorders (i.e. the set is not complete), and if so, return a partial order whose total orders it represents are not covered by the set. If the set is complete return $\text{None}$.

So my question is: is there an efficient way to represent a set of preorders such that I can query the following: "give me a partial preorder such that none of the total preorders it represents are covered by $S$, or if no such preorder exists return $\text{None}$"?

Examples ($U = \{a,b,c\}$):

  • $S = \{a<b\}$, answer = $b<a$ (or $a=b$ or $b<c$ or $b<c<a$ or etc)
  • $S = \{a<b<c\}$, answer = $b<a$ (or $a<c<b$ or etc)
  • $S = \{a<b,b<a,a=b\}$, answer = $\textit{None}$

A naive approach would be to simply enumerate all possible total preorders over $U$, and when adding a preorder to the set we mark all total preorders which contain it as true, and when querying return any total preorder which is yet false, or None of no such order exists. The problem is that there are this many total preorders over a $U$ with $n$ elements [2]!

How can I represent this set of preorders such that this query operation is faster? A trie? Something else? I searched a few books but found nothing on this subject. Really just a place to read about this would be great :)

[1]: "$A$ contains $B$" being equivalent to "$a\mathrel{B}b \implies x\mathrel{A}y$". Sometimes written "$B$ extends $A$". [2]: And also that this returns total preorders, but ideally if the set is e.g. $\{a<b\}$ the algorithm would return e.g. $b<a$, and not a total order.

$\endgroup$
2
  • 1
    $\begingroup$ Given your third example, is it required that the searched preorder is total? Otherwise any order where $a$ and $b$ are not comparable would suffice. Example: $a = (0,1)$, $b = (1, 0)$, $c = (1,1)$; $S=\{R_1, R_2, R_3\}$ where $(x,y) R_1 (z, t) \Leftrightarrow x \leqslant z$, $(x, y) R_2 (z, t) \Leftrightarrow y \leqslant t$ and $(x, y) R_3 (z, t) \Leftrightarrow x+y \leqslant z + t$. Then the answer could be $R_4$ where $(x, y) R_4 (z, t) \Leftrightarrow x \leqslant z \wedge y\leqslant t$ (which does not contain $R_1$, $R_2$ or $R_3$). $\endgroup$
    – Nathaniel
    Commented Nov 13, 2021 at 20:45
  • $\begingroup$ Ah, you're right of course, my definition is no good. I will amend my question. The point here is that a partial preorder "represents" all total preorders in which it's contained. I want to know if there is any total preorder not represented by some partial preorder in the set (return that total ordering or preferrably some partial ordering whose extensions are not represented in the set), or not (return None). $\endgroup$
    – andrepd
    Commented Nov 13, 2021 at 22:20

1 Answer 1

1
$\begingroup$

Let $\phi$ be a CNF on $n$ variables $x_1,\ldots,x_n$. We construct a set of partial preorders over $V = \{a_1,b_1,\ldots,a_n,b_n\}$ as follows:

  • For any $y,z \in V$ such that $y \neq z$, the partial preorder $y = z$.
  • For each $i < n$, the four partial preorders \begin{align} a_i &> a_{i+1} & b_i &> a_{i+1} \\ a_i &> b_{i+1} & b_i &> b_{i+1} \end{align}
  • We translate each clause of $\phi$ into a partial preorder; instead of defining this formally, we give two representative examples: \begin{align} x_1 \lor x_5 \lor x_8 &\Longrightarrow a_1 < b_1 < a_5 < b_5 < a_8 < b_8 \\ x_2 \lor \lnot x_4 &\Longrightarrow a_2 < b_2 < b_4 < a_4 \end{align}

Which total preorders are not covered by this list? In view of the first two items, any such total preorder must be a total order which refines $$ (a_1,b_1) < (a_2,b_2) < \cdots < (a_n,b_n) $$ Conversely, any such total preorder will not be covered by any of the partial preorders appearing in the first two items.

We can convert any such total preorder into a truth assignment: if $a_i < b_i$ then $x_i$ is false, and if $a_i > b_i$ then $x_i$ is true. A total preorder representing the truth assignment $\sigma$ is covered by the partial preorder corresponding to a clause $C$ iff $\sigma$ falsifies $C$. Hence the given set of partial preorders doesn't cover a total preorder iff the total preorder corresponds to a satisfying assignment of $\phi$.

This shows that the decision version of your problem (does there exist a total preorder not covered by any partial preorder in $S$) is NP-hard, and so NP-complete (it is easily shown to be in NP).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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