The problem that I am trying to solve is as follows:
Given a directed graph, find the minimum number of paths that "cover" the entire graph. Multiple paths may go through the same vertice, but the union of the paths should be all of them.
For the given sample graph(see image), the result should be 2 (1->2->4, and 1->2->3 suffice).
By splitting the vertices and assigning a lower bound of 1 for each edge that connects an in-vertex to an out-vertex, and linking a source to every in-vertex and every out-vertex to a sink (they are not shown in the diagram, as it would make the whole thing messy), the problem is now about finding the minimum flow in the graph, with lower bounds constraints.
However, I have read that in order to solve this, I have to find a feasible flow, and then assign capacities as follows : C(e) = F(e) - L(e). However, by assigning a flow of 1 to each Source-vertex edge, vertex-Sink edge, and In-Out edge, the feasible flow is correct, and the total flow is equal to the number of vertices. But by assigning the new capacities, the in-out edges (marked blue) get a capacity of 0 (they have a lower-bound of 1, and in our choosing of a feasible flow, they get a flow of 1), and no flow is possible.
Fig. 2 : How I choose the "feasible flow"
However, from the diagram you can obviously see that you can direct a 2-flow that suffices the lower-bound on each "vertex edge".
Have I understood the minimum flow algorithm wrong? Where is the mistake?!
