An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out that the problem was equivalent to that of computing the width (cardinality of maximum antichain) of a poset.
I know that the problem of computing the width of a poset can be translated into that of finding the size of a maximum matching in a certain bipartite graph, which in turn can be found using the Hopcroft–Karp algorithm, in time $O(n^{5/2})$ (where $n$ is the number of elements in the poset).
To me, that's “polynomial time; end of story''; but to my colleague, who is working with actual data sets, the degree of the polynomial is very important.
My question: what is the current state-of-that art in terms of algorithms for computing the width of a general poset?
Best Answer
For the general case, I believe that there is nothing asymptotically faster than the $O(n^{5/2})$ algorithm that you alluded to. However, if for example the posets in question are known to have small width, then you can do better. See "Recognition algorithms for orders of small width and graphs of small Dilworth number," by Felsner, Raghavan, and Spinrad, Order 20 (2003), no. 4, 351–364. They show that whether a poset has width $k$ can be decided in time $O(kn^2)$. Posets of width at most 3 can be recognized in $O(n)$ time and posets of width at most 4 can be recognized in $O(n\log n)$ time.