G=(V,E) is a directed graph. . A path packing of G is a collection of paths: $\cal{P}=\{ P_1,\dots P_k\}$ such that $V(P_i)\cap V(P_j)=\emptyset$ $\forall i,j$ s.t. $ 1<i<j<k$ where $V(P_i)$ is the set of the points of $P_i$, and $\cup_{i=1}^k V(P_i)=V $
I have to show that the minimum path-packing problem, the problem to find $\cal{P}$ of minimum cardinality, can be solved in an efficient way if the graph is acyclic.
What I'm doing is construct a bipartite graph $G'=(V',E')$ in the following way.
Suppose $ V=\{1,\dots n\}$, then $V'=L\cup R=\{x_1,\dots x_n\}\cup \{y_1,\dots y_n\}$ and $E'=\{(x_i,y_j) | (i,j)\in E\}$, where the $x_i$, $y_i$ are copies of the elements of V.
My idea is that I can solve the problem finding the maximum matching in the bipartite graph and then concatenate the edjes of the matching to built the paths of $\cal{P}$. For example if I have th graph $G=(V,E)$, with $V=\{1,2,3\}, E=\{(1,2),(2,3),(1,3)\}$ we have in the maximum matching the edjes: $(x_1, y_2), (x_2, y_3)$, the path that I obtain doing the concatenation is $(1,2,3)$.
I tried this approch in some examples end it seems to work, but I don't know how to start proving correctnes !
I'm on the right way ? Any hint for the proof ?