Minimum path edge-cover or minimum flow with unit capacities and DAGs I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths from sources si to sinks ti that cover all the edges (ie, any edge is in at least one path).

The problem should be equivalent to a minimum flow problem, after having introduced a virtual source and a virtual sink and having set l(i,j)=1 for i,j not in {s,t} and l(s,si) = l(ti,t)=0 and c(i,j)=infinite.

There is some literature about that (eg, http://basilo.kaist.ac.kr/mathnet/kms_tex/981523.pdf). However, I'd like to know if there is an algorithm that works better in the specific case. The best I can think of is the blocking flow method (see the paper above), which should be O(|V|*|E|) in my case.

Thanks in advance for any help!

Marco
Eventually, I found an answer myself and I used it to implement this bioinformatics library: 

http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract

(see the supplementary data for a theoretical analysis on minimum covering path set).