# Is there fast algorithm for finding min vertex-disjoint path cover of DAG graph of poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v

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.

• Why does it matter that $P$ is a poset of pairs ? That doesn't appear to reveal additional structure Oct 18, 2011 at 18:51
• 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? Oct 18, 2011 at 22:19