7
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – George
    Mar 6, 2012 at 16:53
  • $\begingroup$ What about minimum unsplittable flow? $\endgroup$
    – Nicholas Mancuso
    Mar 6, 2012 at 18:03
  • 2
    $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    Mar 6, 2012 at 18:18
  • $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Sep 15, 2014 at 1:14
  • $\begingroup$ Hi Chao. As for the O() complexity, I have more specific (and better) figures for my specific case, which, roughly, is about layered DAGs: bioinformatics.oxfordjournals.org/content/suppl/2012/04/29/… Moreover, we have chosen the Ford-Fulkerson algorithm, cause it's simple and works well in our typical case (bioinformatics.oxfordjournals.org/content/early/2012/05/02/…). $\endgroup$
    – zakmck
    Sep 16, 2014 at 17:20

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.