Parameterised Approximation and Complexity of Minimum Flow Decompositions

Minimum flow decomposition (MFD) is the strongly NP-hard problem of finding a smallest set of integer weighted paths in a graph G whose weighted sum is equal to a given flow f on G. Despite its many practical applications, we lack an understanding of graph structures that make MFD easy or hard. In particular, it is not known whether a good approximation algorithm exists when the weights are positive.
On the positive side, the main result of this paper is that MFD can be approximated within a factor O(log‖f‖) (where ‖f‖ is the largest flow weight of all edges) times the ratio between the parallel-width of G (introduced by Deligkas and Meir, MFCS 2018) and the width of G (minimum number of paths to cover all edges). In particular, when the MFD size is at least the parallel-width of G, this becomes the first parameterised O(log‖f‖)-factor approximation algorithm for MFD over positive integers. We also show that there exist instances where the ratio between the parallel-width of G and the MFD size is arbitrarily large, thus narrowing down the class of graphs whose approximation is still open. We achieve these results by introducing a new notion of flow-width of (G,f), which unifies both the width and the parallel-width and may be of independent interest.
On the negative side, we show that small-width graphs do not make MFD easy. This question was previously open, because width-1 graphs (i.e. paths) are trivially solvable, and the existing NP-hardness proofs use graphs of unbounded width. We close this problem by showing the tight results that MFD remains strongly NP-hard on graphs of width 3, and NP-hard on graphs of width 2 (and thus also parallel-width 2). Moreover, on width-2 graphs (and more generally, on constant parallel-width graphs), MFD is solvable in quasi-polynomial time on unary-coded flows.