# How to find the set of edges for the directed graph associated with a partial order?

I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$, where $f(a,b) = true$ if and only if $a\preceq b$. Given this setup, I can construct a directed graph $D = (S, E)$, where $E= \{(a,b) \in S\times S | f(a,b) = true\}$. I can find all the elements of $E$ in time $|S|^2/2$ by examining all the possibilities. I am looking for an algorithm that can take advantage of the properties of partial order (in particular, transitivity), to reduce the expected time to find all the elements of $E$ to a linear order function of $|S|$.

• The size of the output is $\Theta (|S|^2)$ in the worst case. So the algorithm needs time $\Theta (|S|^2)$ just to print the output. – Yury Sep 29 '13 at 16:56
• You're right. I should ask for $O(|S|)$ in the average case. – user765195 Sep 29 '13 at 16:59
• How do you define the “average case”? What is the output size in the average case? – Yury Sep 29 '13 at 17:23

As Yury already mentioned, the output size can be too large to hope for subquadratic time, when measured as a function of the input size $n$. But even when the output size is small, very little can be done. In particular, suppose that the input is a partial order with a single comparable pair, chosen uniformly at random among all such partial orders. Then the output size is $O(1)$ but nevertheless it takes $\Omega(n^2)$ queries to find the comparable pair. This is true regardless of whether you're considering only deterministic algorithms or whether you're doing expected case analysis of randomized algorithms.