While greedy-weight is most commonly used in applications,
the approach was first presented as part of a general framework [1]}: pick any optimality criteria
for \(s\) -\(t\)  paths that is saturating (i.e., fully decomposes at least one edge), and successively remove
optimal paths. Since each path is saturating, the algorithm must decompose the flow in \(m\)  or fewer paths.
Another optimality criterion sometimes used in DNA assembly (e.g., in vg-flow [2]})
is the longest path (with its maximum possible flow so that it is saturating). To adapt our construction of \((G_\ell , X_{\ell ,2^{\ell +1}})\)  so that this approach has the same approximation ratio, consider \((G_\ell ^*, X_{\ell , 2^{\ell +1}}^*)\) ,
constructed as in \((G_\ell , X_{\ell ,2^{\ell +1}})\)  except that we replace every backbone edge \((u,v)\)  with two edges,
\((u,w)\)  and \((w,v)\) . See fig:greedy:gstar in app:figures for an example.
Then a path along the backbone edges will be the longest from \(s\)  to \(t\)  and the above asymptotic analysis holds,
since we no more than doubled the number of edges.
Yet another optimality criterion, studied in [3]} for its application to network routing,
is the shortest path (again with its maximum possible
flow). \((G_\ell ^*\) , \(X_{\ell , 2^{\ell +1}}^*)\)  will also force this approach to take an exponential number of paths, since first the algorithm will
take all \(2^{\ell +1}\)  weight-1 edges with \(2^{\ell +1}\)  different paths.
