<p>Eventually, I found an answer myself and I used it to implement this bioinformatics library: </p>

<p><a href="http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract" rel="nofollow noreferrer">http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract</a></p>

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

CC BY-SA 3.0
2012-05-14T17:41:31.453Z
2017-10-08T16:40:10.313Z
2017-10-08T16:40:10.313Z
zakmck
<p>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).</p>

<p>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.</p>

<p>There is some literature about that (eg, <a href="http://basilo.kaist.ac.kr/mathnet/kms_tex/981523.pdf" rel="nofollow">http://basilo.kaist.ac.kr/mathnet/kms_tex/981523.pdf</a>). 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.</p>

<p>Thanks in advance for any help!</p>

<p>Marco</p>

CC BY-SA 3.0
2012-03-06T16:53:04.787Z
Something I don't understand in the paper is that the authors state that the minimum flow of a network equals the capacity of the maximum cut. Then they present a polynomial time algorithm which solves it. However, the max-cut problem is NP-complete, so there must be a mistake somewhere, or maybe I didn't understand something.
George
CC BY-SA 3.0
2012-03-06T18:03:53.000Z
What about minimum unsplittable flow?
Nicholas Mancuso
CC BY-SA 3.0
2012-03-06T18:18:50.177Z
@GeorgeB. the way they define the weight of a cut, all edge weights are negative, since they are equal to the lower bound for the edge minus the capacity of the edge. so this is a max cut problem on a graph where *all* edges have negative weights, i.e. it is a min cut problem.
Sasho Nikolov
CC BY-SA 3.0
2014-09-15T01:14:57.633Z
In the literature you mentioned, there is a section showing the problem actually reduces to unit capacity max flow. Dinic's algorithm would run in $O(n^{2/3} m)$ time.
Chao Xu
CC BY-SA 3.0
2014-09-16T17:20:27.227Z
Hi Chao. As for the O() complexity, I have more specific (and better) figures for my specific case, which, roughly, is about layered DAGs: http://bioinformatics.oxfordjournals.org/content/suppl/2012/04/29/bts258.DC1/supplemental_material_v1_1.pdf Moreover, we have chosen the Ford-Fulkerson algorithm, cause it's simple and works well in our typical case (http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract).
zakmck
<ds.algorithms><graph-theory><max-flow>
Minimum path edge-cover or minimum flow with unit capacities and DAGs
zakmck
# Minimum path edge-cover or minimum flow with unit capacities and DAGs

(Asked by: username_0 on 2011-08-05)

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

**Tags:** ds.algorithms, graph-theory, max-flow

> **Comments:**
> **username_1**: Something I don't understand in the paper is that the authors state that the minimum flow of a network equals the capacity of the maximum cut. Then they present a polynomial time algorithm which solves it. However, the max-cut problem is NP-complete, so there must be a mistake somewhere, or maybe I didn't understand something.  
> **username_2**: What about minimum unsplittable flow?  
> **username_3**: @username_1B. the way they define the weight of a cut, all edge weights are negative, since they are equal to the lower bound for the edge minus the capacity of the edge. so this is a max cut problem on a graph where *all* edges have negative weights, i.e. it is a min cut problem.  
> **username_4**: In the literature you mentioned, there is a section showing the problem actually reduces to unit capacity max flow. Dinic's algorithm would run in $O(n^{2/3} m)$ time.  
> **username_0**: Hi Chao. As for the O() complexity, I have more specific (and better) figures for my specific case, which, roughly, is about layered DAGs: http://bioinformatics.oxfordjournals.org/content/suppl/2012/04/29/bts258.DC1/supplemental_material_v1_1.pdf Moreover, we have chosen the Ford-Fulkerson algorithm, cause it's simple and works well in our typical case (http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract).  

---

## 1 answers

### Answer by username_0 on 2012-05-14. Score: 1 | Accepted answer

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).


---

