Minimum flow decomposition (MFD) is the problem of finding a smallest sized decomposition
of a network flow \(X\)  on directed graph \(G=(V,E)\)  into weighted source-to-sink
paths whose superposition equals \(X\) .
We focus on the case where path weights are restricted to be integers.
It is a textbook result [1]} that if \(G\)  is acyclic (a DAG) a decomposition using no more than \(m = |E|\)  paths
always exists.
However, MFD is strongly NP-hard [2]}, even on DAGs, and even when the flow values come
only from \(\lbrace 1, 2, 4\rbrace \)  [3]}. Recent work has shown that the problem is FPT in the size of the
minimum decomposition [4]}
and that it can be formulated as an ILP of quadratic size [5]}.
