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

$\endgroup$
  • 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 '12 at 16:53
  • $\begingroup$ What about minimum unsplittable flow? $\endgroup$ – Nicholas Mancuso Mar 6 '12 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 '12 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 '14 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 '14 at 17:20
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).

$\endgroup$

Your Answer

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

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