1
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yury Sep 29 '13 at 16:56
  • $\begingroup$ You're right. I should ask for $O(|S|)$ in the average case. $\endgroup$ – user765195 Sep 29 '13 at 16:59
  • 2
    $\begingroup$ How do you define the “average case”? What is the output size in the average case? $\endgroup$ – Yury Sep 29 '13 at 17:23
8
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

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.