10
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.