Berge's Conjecture on Directed Path Partitions - A Survey <s> Linear Programming. <s> Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof. <s> BIB001 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Linear Programming. <s> For an acyclic digraph G and positive integer k , we give a min-max equality for: minimum { k ℘ + V ( G ) − ∪ ℘ } : ℘ is a node-disjoint set of dipaths in G } We prove that there exist k independent sets { S j : j = 1, 2,..., k } such that for every optimum ℘, every P ∈℘; intersects each S j , and every dipath P in G −∪℘; intersects | P | different sets S j . <s> BIB002
Several researchers (see BIB001 , BIB002 ,  , and  ) used LP techniques to extend the theorem of Greene and Kleitman to acyclic digraphs. We shall describe here the recent proof suggested by Pierre Charbit [26] . Let G = (V, E) be an acyclic digraph where |V | = n. First, we modify the graph G in order to construct G ′ in the following way: add a new vertex v 0 to G, and add a double edge from v 0 to every vertex of G. Finally we add a loop for every vertex of G. Now, since G is acyclic, a path partition of G is a cycle cover of G ′ , where all cycles greater than one go through v 0 , and no two cycles have any other common vertex. We define the classic linear program of finding an integer flow of G ′ such that all vertices v i , i ≥ 1, have out flow of value one. Define the following matrix: We now define vectors b = (b 1 , . . . , b 2n ) and c = (c 1 , . . . , c |E(G ′ )| ) as follows: Consider the linear program (P): Since the matrix A is totally unimodular, there exist integral optimal solutions to (P). The system of constraints MX = 0 expresses the fact that these solutions represent integral flows on the vertices of G (and thus of G ′ ), in other words, a family of cycles. Moreover, the system M + X = 1 implies that these cycles go exactly once through each vertex of G. Since G is acyclic, all the cycles in G ′ meet v 0 and, therefore, represent paths of G. This proves that optimal solutions of (P) are exactly path partitions of G. Furthermore, the objective function counts k times the number of cycles that go through x 0 and one for each loop. So for the path partition it counts k times the number of paths of length more than one plus one for each path of length zero (an isolated vertex). It is then clear that a solution that minimizes this objective function is a k-optimal path partition and the value of the objective function is its k-norm. Consider now the dual problem. The variables of the problem are two vectors y and z corresponding to the vertices of V (G) and we want to maximize  We associate a k-colouring C k = {C 1 , C 2 , . . . , C k } to such a solution in the following way: Let Note that if vertices i, j ∈ C r , y i + z j − z i = 1 and by  , that means that C r is an independent set and C k is indeed a k-colouring. We shall now show that C k is orthogonal to every k-optimal path partition P in G. Being a k-optimal path partition, P is represented by a vector x ∈ N E(G ′ ) which is a solution of the primal problem. Complementary slackness conditions means that if an entry of x is non zero then the corresponding inequality constraint in the dual is an equality. Let P be a short path, i.e., a path in P 0 . We have seen that such paths are represented in x by the loops on vertices i ∈ P . So if i ∈ P , by complementary slackness, we get y i = 1, and since by (2) we have y i ≤ z i ≤ k, we know that i belongs to some C r . Furthermore, if (i, j) ∈ E and i ∈ C r , then by (2), z j − z i ≤ −y i = −1, implying that the colours in P are strictly decreasing. Assume now that P is a long path. To simplify the notations, assume that P = (v 1 , . . . , v l ). We have seen that in the primal problem P is represented by a cycle going through v 0 . Thus, again, by complementary slackness, we know that equality is satisfied in all the constraints of (2) corresponding to edges of this cycle. Then But y i is at most 1. Since the variable z i starts at k and finishes at 1, it has to take all values between these two. Thus for each p, 1 ≤ p ≤ k, we can define i p = max{1 ≤ i ≤ l; z i = p}. But this implies that z ip+1 = p − 1 (if z ip+1 ≥ p then it means that there exists j > i p such that z j = p, which contradicts the maximality of i p ). So y ip = 1, implying that for each p, v ip ∈ C p . In other words, P meets all k colours in C k . This completes the proof that C k is orthogonal to every k-optimal path partition P. Cameron  gave a common extension of the Greene-Kleitman Theorem and Greene's Theorem (Theorem 3.6 in Section 3) using a different linear program. More related work appears in BIB002   .