5
$\begingroup$

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

|cite|improve this question
$\endgroup$
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Dont you need an extra logarithmic factor for transitivity? $\endgroup$ – Ariel Oct 17 '16 at 14:11
  • 1
    $\begingroup$ @Ariel I don't think so. $\endgroup$ – Yuval Filmus Oct 17 '16 at 14:21
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Oct 12 '16 at 5:00
  • $\begingroup$ @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. $\endgroup$ – Thomas Klimpel Oct 12 '16 at 5:39

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.