<p>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.</p>

CC BY-SA 3.0
2013-09-29T20:06:33.400Z
2013-09-29T20:06:33.400Z
David Eppstein
<p>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|$.  </p>

CC BY-SA 3.0
2013-09-29T16:56:26.767Z
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
CC BY-SA 3.0
2013-09-29T16:59:11.323Z
You're right. I should ask for $O(|S|)$ in the average case.
user765195
CC BY-SA 3.0
2013-09-29T17:23:19.897Z
How do you define the “average case”? What is the output size in the average case?
Yury
<graph-algorithms><directed-acyclic-graph><partial-order>
How to find the set of edges for the directed graph associated with a partial order?
user765195
# How to find the set of edges for the directed graph associated with a partial order?

(Asked by: username_0 on 2013-09-29)

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

**Tags:** graph-algorithms, directed-acyclic-graph, partial-order
> **Comments:**
> **username_1**: 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.  
> **username_0**: You're right. I should ask for $O(|S|)$ in the average case.  
> **username_1**: How do you define the “average case”? What is the output size in the average case?  

---

## 1 answers

### Answer by username_2 on 2013-09-29. Score: 8 | Accepted answer

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.


---

