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.

StackExchange Computer Science Q#64501, answer score: 4