## 2 The One Row Restriction of the MCSP as a Network Optimization Problem
Traversing an arc \(((j;q_{1},\ldots,q_{H}),(j+1;q^{\prime}_{1},\ldots,q^{\prime}_{H}))\) in the network means that in the corresponding decomposition of \(A\) there are exactly \(q_{w}\) segments with a coefficient equal to \(w\) and a 1 in position \(j\) and exactly \(q^{\prime}_{w}\) segments with a coefficient equal to \(w\) and a 1 in position \(j+1\), for all \(w\in[H]\). As an example, Figure 2 shows the network corresponding to the row vector  
\[A=\left( \begin{array}{cccc}2&3&2&3\end{array} \right) \tag{12}\]  
It is worth noting that, as we want to minimize the number of segments in the decomposition, whenever we cross arc \(((j;q_{1},\ldots,q_{H}),(j+1;q^{\prime}_{1},\ldots,q^{\prime}_{H}))\) we use \(\max\{0,q_{w}-q^{\prime}_{w}\}\) segments with a coefficient equal to \(w\), a 1 in position \(j\) and a zero in position \(j+1\); \(\min\{q_{w},q^{\prime}_{w}\}\) segments with a coefficient equal to \(w\) and a 1 in both positions \(j\) and \(j+1\) and finally \(\max\{0,q^{\prime}_{w}-q_{w}\}\) segments with a coefficient equal to \(w\), a zero in position \(j\) and a 1 in position \(j+1\). Hence, passing from the vertex  
Figure 2: The partition network corresponding to the row \((2\,;3\,,2\,,3)\) with some lengths on arcs. The first two vertices on the right of \(s\) correspond to the two possible partitions of 2 (_i.e._, \(2=1+1\) and \(2=2\)). The subsequent three vertices on the right correspond to the three possible partitions of 3 (_i.e._, \(3=1+1+1\), \(3=1+2\), \(3=3\)), and so on. Note that the entries of two subsequent columns, say \(j\) and \(j+1\), in the row vector \(A\) induce a bipartite subnetwork in \(D\). The dotted arcs represent the shortest \(s-t\) path in \(D\). Similarly, the set \(\mathcal{A}_{i}\) includes an arc for each pair of vertices corresponding to consecutive entries on the same row:  
\[\mathcal{A}_{i} := \{(s_{i},(i,1;q_{1},\ldots,q_{H})):(i,1;q_{1},\ldots,q_{H})\in V_{i}\} \tag{18}\] \[\cup\{((i,j;q_{1},\ldots,q_{H})\,,(i,j+1;q^{\prime}_{1},\ldots,q^{ \prime}_{H})):j\in[n-1]\] (19) \[(i,j;q_{1},\ldots,q_{H})\,,(i,j+1;q^{\prime}_{1},\ldots,q^{\prime }_{H})\in V_{i}\} \tag{20}\]  
Consider the combined partition network \(D=(V,\mathcal{A})\) having as vertexset  
\[V=\{s\}\cup\bigcup_{i\in[m]}V_{i}\cup\{t\} \tag{21}\]  
and as arxset  
\[\mathcal{A}=\{(s,s_{i}):i\in[m]\}\cup\bigcup_{i\in[m]}\mathcal{A}_{i}\cup\{(i,n;q_{1},\ldots,q_{H})\,,t):i\in[m]\} \tag{22}\]  
\(D\) contains a vertex corresponding to each possible partition of each entry \(a_{ij}\) of \(A\). Each of these vertices is denoted by \((i,j;q_{1},\ldots,q_{H})\), where \((i,j)\) denotes the position of \(a_{ij}\) in \(A\), and \(q_{w}\) denotes the number of terms equal to \(w\) in the extended form of the corresponding partition of \(a_{ij}\) or, equivalently, the coefficient of \(w\) in its compact form, meaning \(a_{ij}=\sum_{w=1}^{H}q_{w}\cdot w\). As an example, Figure 3 shows the combined partition network corresponding to the intensity matrix  
\[A = \left( \begin{array}{cc}2&3\\ 3&1\end{array} \right) \tag{23}\]  
Figure 3: The combined partition network for matrix Equation (23). The dotted arcs represent a flow in the network that encodes a possible decomposition of \(A\). It is worth noting that, as for the one row restriction, a decomposition of the \(i\)-th row of \(A\) corresponds by construction to a path in the network \(D_{i}\). In particular, traversing a vertex \((i,j;q_{1},\ldots,q_{H})\) means that in the decomposition, there are exactly \(q_{w}\) matrices with a coefficient equal to \(w\) and a 1 in position \((i,j)\), for all \(w\in[H]\). Let \(\ell:\mathcal{A}\longrightarrow\mathbb{Z}_{+}^{H}\) be a function that associate a \(H\)-dimensional _length vector_ to each arc  
\[\alpha=\left(\left(i,j;q_{1},\ldots,q_{H}\right),\left(i,j+1;q_{1}^{\prime}, \ldots,q_{H}^{\prime}\right)\right)\in\mathcal{A} \tag{24}\]  
according to the following law:  
\[\ell(\alpha)=