1
$\begingroup$

Let $\preceq$ be a partial order on a finite set $X$. Is there an algorithm with time complexity $O(|X|^{2})$ which can compute a linear extension $\leq$ for the partial order $\preceq$ on $X$?

$\endgroup$
1
  • 1
    $\begingroup$ It would improve your Question to add a few words about how you became interested in this problem. I am fond of the term topological sort for such algorithms. $\endgroup$ – hardmath Jan 13 '20 at 15:44
3
$\begingroup$

Yes. Your problem can be reduced to computing a topological ordering of a directed acyclic graph $D = (X, A)$, where $X$ is the finite set and there is an arc $\overrightarrow{xy}$ in $A$ iff $x \preceq y$. There is a simple $O(|X| + |A|)$-time algorithm to compute a topological ordering which can be found in most algorithms textbooks. See, for example, section 6.3 of Erickson's book.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.