How to efficiently determine whether a relation is total?

I have a set $S$ of pairs $(x_1,x_2)$ with $x_1,x_2 \in X$ for some set $X$.

I want to know whether this defines a total relation on $X$. In other words, whether:

• If $(a,b)$ in $S$ and $(b,c)$ in $S$, then $(a,c)$ in $S$. (transitivity)
• Exactly one of $(a,b)$ and $(b,a)$ is in $S$ unless $a=b$, in which case they are both an element of $S$. (totality and antisymmetry)

Brute-force would take $O(|X|^3|S|)$ steps (I think), because there are $|X|^3$ triples $(a,b,c)$ and looking up whether something is an element of an array costs $O(|S|)$.

A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$.

You can improve the running time of transitivity checking to $O(|X|^\omega)$, where $\omega$ is the matrix multiplication constant; I'll let you figure out how.

• Dont you need an extra logarithmic factor for transitivity? Oct 17, 2016 at 14:11
• @Ariel I don't think so. Oct 17, 2016 at 14:21

If $S$ is a total (order) relation, then $|S|=|X|(|X|+1)/2$. If you start by checking that $S$ has at least size $|X|(|X|+1)/2$, then you don't really lose anything by constructing a matrix corresponding to your relation as Yuval suggested. Checking antisymmetry (and reflexivity) is no issue either. You can then try to sort $X$ according to $S$ as represented by the matrix with a suitable well behaved sorting algorithm (for example the $n \log n$ algorithms merge sort or heap sort would work). We can check in time $O(|X|^2)$ whether the result is sorted. If that algorithm succeeded in sorting $X$, then $S$ is a total (order) relation, otherwise it is not. The total runtime is $O(|S|)$ if $|S|<|X|(|X|+1)/2$ and $O(|X| \log |X| + |S|+|X|^2) = O(|S|)$ otherwise. This is optimal, if $S$ is given as a list. (On the other hand, if $S$ is given as the transitive closure of a given DAG, then it is sometimes possible to do this faster.)

• Interesting approach. Do you have a proof or justification for the statement "If that algorithm succeeds in sorting X, then... otherwise..."? I'm skeptical. Your algorithm won't look at the entire matrix: it'll look at only $O(n \lg n)$ entries, out of the $n^2$ entries in the matrix (where $n=|X|$). Thus, if any of the entries it doesn't look at are wrong (inconsistent with transitivity), then it seems like your algorithm won't detect that.
– D.W.
Oct 12, 2016 at 5:00
• @D.W. The check whether $|X|$ fails to be sorted has to be done after a suitable algorithm tried to sort it. This looks at all entries of the entire matrix, and takes $O(|S|)$ steps. Hence the total runtime is $O(|S|)$, as stated. Oct 12, 2016 at 5:39