<p>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.</p>

CC BY-SA 3.0
2011-10-18T22:26:01.963Z
thank you! I think, I've got the idea. The notion of "layers of maxima" was the thing I could not express myself before.
StuL
CC BY-SA 3.0
2011-10-18T20:01:04.037Z
2011-10-18T20:01:04.037Z
David Eppstein
<p>Let P is a poset of pairs (x, y) where (x, y) &lt; (u, v) iff x &lt; u and y &lt; v. Let G is a DAG corresponding to poset P. Suppose I want to find some minimum vertex-disjoint path cover of G.</p>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2011-10-18T18:51:51.603Z
Why does it matter that $P$ is a poset of pairs ? That doesn't appear to reveal additional structure
Suresh Venkat
CC BY-SA 3.0
2011-10-18T22:19:13.927Z
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?
StuL
<ds.algorithms><co.combinatorics><graph-algorithms>
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
StuL
# 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

(Asked by: username_0 on 2011-10-18)

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.

**Tags:** ds.algorithms, co.combinatorics, graph-algorithms
> **Comments:**
> **username_1**: Why does it matter that $P$ is a poset of pairs ? That doesn't appear to reveal additional structure  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_2 on 2011-10-18. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: thank you! I think, I've got the idea. The notion of "layers of maxima" was the thing I could not express myself before.  

---

