Minimum cost flow decomposition on arc-coloured networks

A network N is formed by a (multi)digraph D together with a capacity function u : A ( D ) → R + , and it is denoted by N = ( D , u ) . A flow on N is a function x : A ( D ) → R + such that x ( a ) ≤ u ( a ) for all a ∈ A ( D ), and it is said to be k -splittable if it can be decomposed into up to k paths. We say that a flow is λ -uniform if its value on each arc of the network with positive flow value is exactly λ , for some λ ∈ R + * . We consider the problem of decomposing a flow over an arc-coloured network with minimum cost, that is, with minimum sum of the cost of its paths, where the cost of each path is given by its number of colours. We show that this problem is NP -Hard for general flows on networks. When we restrict the problem to λ -uniform flows, we show that it can be solved in polynomial time for networks with at most two colours. Moreover, we prove that it is NP -Hard for general networks with three colours and for acyclic networks with at least five colours.