Minimum path covering problem We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the following:

Let $k$ be some integer, and let $Z_k$ be a graph containing $\frac{k(k+1)}{2}$ vertices.
We label each vertex with a couple $(i,j)$ such that $1 \leq i \leq j \leq k$.
Hereafter, we name vertices using their label.
The set of edges in $Z_k$ is defined as follows  : 
$\{ ((i,j),(i&#39;,j&#39;)) | i&#39; &gt;i \land j&#39; \geq i \}$.

What is the minimal path covering of $Z_k$ ? 

Reading 
"On Path Cover Problems in Digraphs and Applications to Program Testing"
by Ntafos et al. , we have seen that the minimal path covering equals
the cardinal of the greatest incomparable vertex set.
We were thinking about the following set:
$S= \{ (i,j) : i \geq k/2 \land j &lt; k/2 \}$
which has a cardinal of $\frac{k^2}{4}-\frac{k}{2}$.

Sincerely,

Pierre
It sounds like your graph is a transitively closed DAG, right? If so (and this is probably a restatement of what you say in your citation of Ntafos et al) the minimum number of paths needed to cover the DAG is just the maximum number of pairwise incomparable elements; this is Dilworth's theorem.

Your example may be simple enough that one can identify this maximum incomparable set directly, but in general it is possible to find this set in polynomial time, by an algorithm based in graph matching. The "Proof via König's theorem" section of the Wikipedia article on Dilworth's theorem explains how.