Just like its more common node variant, \(\textsf {width}(G)\)  can be computed
in \(O(mn)\)  time. As described by, e.g., [1]}, [2]},
this is done by reduction to a min-flow instance with demand one on every edge;
the minimum flow of this instance is \(\textsf {width}(G)\) , and the flow can be found by reduction
to a max-flow instance.
Moreover, the problem can be relaxed to only require the coverage of \(S\subseteq E\)  and solved in the same running time by setting the demands only on the edges of \(S\) .
