<p>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 <a href="http://en.wikipedia.org/wiki/Dilworth%27s_theorem">Dilworth's theorem</a>.</p>

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

CC BY-SA 2.5
2011-03-12T23:44:47.283Z
2011-03-12T23:44:47.283Z
David Eppstein
<p>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:</p>

<p>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 \}$.</p>

<p>What is the minimal path covering of $Z_k$ ? </p>

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

<p>Sincerely,</p>

<p>Pierre</p>

CC BY-SA 2.5
2011-03-13T20:39:10.677Z
should it be $j' \ge j$ instead of $j' \ge i$  in the definition of an edge of $Z_k$ ?
Suresh Venkat
<graph-theory><co.combinatorics><application-of-theory>
Minimum path covering problem
Pierre 
# Minimum path covering problem

(Asked by: username_0 on 2011-03-12)

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

**Tags:** graph-theory, co.combinatorics, application-of-theory

> **Comments:**
> **username_1**: should it be $j' \ge j$ instead of $j' \ge i$  in the definition of an edge of $Z_k$ ?  

---

## 1 answers

### Answer by username_2 on 2011-03-12. Score: 10

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](http://en.wikipedia.org/wiki/Dilworth%27s_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.


---

