5
$\begingroup$

Let P is a poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v. Let G is a DAG corresponding to poset P. Suppose I want to find some minimum vertex-disjoint path cover of G.

It is known that there is a general algorithm by reduction of this problem to maximal matching. But in this case P may have some specific properties, so may be there is some algorithm for doing this faster than matching.

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ Why does it matter that $P$ is a poset of pairs ? That doesn't appear to reveal additional structure $\endgroup$ – Suresh Venkat Oct 18 '11 at 18:51
  • 2
    $\begingroup$ I think there is no representation of poset $2^{\{1, 2, 3\}}$ as points in the plane. So there is some additional structure. Am I mistaken? $\endgroup$ – Valeriy Sokolov Oct 18 '11 at 22:19
7
$\begingroup$

So if I'm interpreting your question you have a set of points in the Euclidean plane and you want to find a decomposition of the points into as few monotone chains as possible? This is called the "layers of maxima" problem and it is easily solved in time O(n log n) by a plane sweep algorithm that sweeps over the points from left to right, using a binary search tree to maintain the set of intersection points of the monotone chains with the sweep line and assigning each point in sweep order greedily to the highest monotone chain that it can be assigned to. See e.g. Buchsbaum and Goodrich, "Three-Dimensional Layers of Maxima", Algorithmica 2004, for a three-dimensional version that can still be solved in O(n log n) and references to earlier work on the problem.

$\endgroup$
1
  • $\begingroup$ thank you! I think, I've got the idea. The notion of "layers of maxima" was the thing I could not express myself before. $\endgroup$ – Valeriy Sokolov Oct 18 '11 at 22:26

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.