# 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',j')) | i' >i \land j' \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 < k/2 \}$ which has a cardinal of $\frac{k^2}{4}-\frac{k}{2}$.

Sincerely,

Pierre

• should it be $j' \ge j$ instead of $j' \ge i$ in the definition of an edge of $Z_k$ ? – Suresh Venkat Mar 13 '11 at 20:39