## 2 The One Row Restriction of the MCSP as a Network Optimization Problem
\begin{cases}\left(q_{1},\ldots,q_{H}\right)&\text{if }\alpha=\left(s_{i}, \left(i,1;q_{1},\ldots,q_{H}\right)\right)\text{, }i\in[m]\\ \left(\max\left\{0,q_{1}^{\prime}-q_{1}\right\},\ldots,\max\left\{0,q_{H}^{ \prime}-q_{H}\right\}\right)&\text{if }\alpha=\left(\left(i,j;q_{1},\ldots,q_{H}\right), \left(i,j+1;q_{1}^{\prime},\ldots,q_{H}^{\prime}\right)\right)\\ &i\in[m]\text{, }j\in[n-1]\\ \left(0,\ldots,0\right)&\text{otherwise.}\end{cases} \]  
In particular, we use the convention to associate the length vector \(\left(0,\ldots,0\right)\) to both the arcs leaving the source vertex \(s\) and the arcs entering the sink vertex \(t\). For all the remaining arcs, the \(w\)-th entry of the length vector, denoted as \(\ell_{w}(\alpha)\), represents the coefficient of \(w\) in the compact form of the corresponding partition of \(a_{i,j+1}=\sum_{w=1}^{H}q_{w}^{\prime}\cdot w\) minus the coefficient of \(w\) in the compact form of the corresponding partition of \(a_{ij}=\sum_{w=1}^{H}q_{w}\cdot w\), _i.e._, \(\ell_{w}(\alpha):=\max\left\{0,q_{w}^{\prime}-q_{w}\right\}\). As an example, Figure 4 provides the length vector of (certain arcs of) the partition network corresponding to the first row of matrix Equation (23), namely \((2\;3)\). It is easy to realize that any integral \(s-t\) flow of value \(m\) in the combined partition network \(D\) associated to a given intensity matrix \(A\), _i.e._, a \(s-t\) flow in \(D\) composed by a family of \(s_{i}-t\) flows, each  
Figure 4: The arc \(\left((1,1;0,1,0),(1,2;3,0,0)\right)\) represents a decomposition of the row vector \((2\;3)\) in which entry 2 is decomposed by means of one segment having coefficient 2 and entry 3 is decomposed by means of three segments having coefficients 1. In order to move from partition \(2=2\) to partition \(3=1+1+1\), we need three new segments with a coefficient 1 and no segment with coefficient 2 or 3.  
lying in the subnetwork \(D_{i}\), corresponds to a decomposition of the intensity matrix \(A\). Any such flow is a combination of \(m\) paths \(p_{1},\ldots,p_{m}\) such that each \(p_{i}\) is a \(s-t\) path in the network \(D_{i}\), for all \(i\in[m]\). The length vector associated to this \(s-t\) flow is  
\[\max_{i\in[m]}\left(\sum_{\alpha\in p_{i}}\ell(\alpha)\right):= \left(\max_{i\in[m]}\left\{\sum_{\alpha\in p_{i}}\ell_{1}(\alpha)\right\}, \ldots,\max_{i\in[m]}\left\{\sum_{\alpha\in p_{i}}\ell_{H}(\alpha)\right\}\right) \tag{25}\]  
Note that the \(w\)-th component of vector Equation (25) provides the overall number of segments with a coefficient \(w\) in the decomposition of \(A\). Hence, solving the MCSP is equivalent to find a \(s-t\) flow of value \(m\) (that is, paths \(p_{1},\ldots,p_{m}\)) such that the sum of all components of Equation (25) is minimized, or equivalently  
\[\min\sum_{w=1}^{H}\max_{i\in[m]}\left(\sum_{\alpha\in p_{i}}\ell_ {w}(\alpha)\right) \tag{26}\]  
over all \(s-t\) paths \(p_{1},\ldots,p_{m}\) in \(D_{1},\ldots,D_{m}\). By referring to matrix Equation (23) and to the corresponding combined partition network shown in Figure 3, the length vector of the top-most dotted path \(p_{1}\) equals \((2,0,0)+(0,1,0)=(2,1,0)\) and the length vector of the bottom-most dotted path \(p_{2}\) equals \((1,1,0)\) + \((0,0,0)\) = \((1,1,0)\). The length vector of the whole flow equals \((2,1,0)\). Given paths \(p_{1}\) and \(p_{2}\), we can build the corresponding decomposition of the matrix \(A\) in the following way. For each component \(w\), consider a nonnegative integer \(m\times n\) matrix \(A_{w}\) having the generic entry \((i,j)\) equal to the component \(q_{w}\) in vertex \((i,j;q_{1},\cdots,q_{H})\) belonging to \(p_{i}\). Then, the matrix \(A\) can be decomposed as  
\[A=\sum_{w=1}^{H}w\cdot A_{w} \tag{27}\]  
As an example, by referring to the matrix Equation (23) and to the corresponding combined partition network shown in Figure 3, this procedure leads to the following decomposition of \(A\):  
\[A = \left( \begin{array}{cc}2&3\\ 3&1\end{array} \right)=1\left( \begin{array}{cc}2&1\\ 1&1\end{array} \right)+2\left(