Multiroute flows: Cut-trees and realizability

In the context of q-route flows in an undirected network with non-negative edge capacities, for integer values of q⩾2, we consider two problems of both theoretical and practical interest. The first problem focuses on investigating the existence and construction of a cut-tree. For q=2, we show that a cut-tree always exists and can be constructed in strongly polynomial time. However, for q⩾3, in general, a cut-tree does not exist and we establish this through a counter-example. The second problem addresses the issue of checking if a given matrix R is 2-realizable-that is, checking if there exists an undirected, simple network with non-negative edge capacities such that the non-diagonal elements of R are precisely the maximum 2-route flow values between corresponding pairs of nodes in the network. We provide a complete characterization of 2-realizable matrices and using this characterization, we prove that the problem of testing if a given matrix is 2-realizable is, in general, NP-complete.