15
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Just to clarify: When you say that your colleague's problem is "equivalent", how strong is the notion of "equivalence"? Do we really have to worry about worst-case posets or will only certain special kinds of posets arise in the application? $\endgroup$
    – Timothy Chow
    Commented Dec 9, 2014 at 0:35
  • 1
    $\begingroup$ The problem starts out with an arbitrary Directed Acyclic Graph; the parameter of interest turns out to be the size of a maximum antichain in the associated reachability partial order. So as far as I understand, all finite posets are in play. $\endgroup$
    – David Galvin
    Commented Dec 9, 2014 at 1:55

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .