1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ is a family of paths, sorry it wasn't clear! $\endgroup$ – user269663 Nov 6 '15 at 11:44
  • $\begingroup$ $L=\{x_1,\dots x_n\}$ and $L=\{y_1,\dots y_n\}$ where the only thing that you know is that they are of the same cardinality of V . $\endgroup$ – user269663 Nov 6 '15 at 13:50
  • $\begingroup$ .And my idea is to built $\cal{P}$ as : $P_i=(x_i,y_j)\cup (x_j,y_k) \cup (x_k,y_h) \dots $ , if all of this edjes are in the graph. $\endgroup$ – user269663 Nov 6 '15 at 13:57
  • $\begingroup$ I think it would improve your Question to include these details in its body. Note that what you've written is not (on its face) a path, since $y_j\neq x_j$, etc. $\endgroup$ – hardmath Nov 6 '15 at 17:35
  • $\begingroup$ what I meant is that $x_i$ and $y_j$ are copies of the elements of V $\endgroup$ – user269663 Nov 6 '15 at 17:41

Your Answer

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

Browse other questions tagged or ask your own question.