We study an optimization problem which can be interesting in several network applications, especially in telecommunication. Given a capacitated directed network G in which a flow, related to a certain commodity, has to be sent from a given set of origins to a given set of destinations, we want to compute a maximum congested cut, i.e., a cut (S,T) of G which maximizes the ratio between the net demand of T and the capacity of the cut. We will show that a maximum congested cut can be computed in polynomial time by formulating the problem as a special maximum mean-weight cut problem, and solving it by Newton's method for linear fractional combinatorial optimization. The introduced formulation will be extended to the case in which the flow demands vary in a polyhedron D, and a cut has to be determined which maximizes the congestion with respect to the flow demands in D, addressing a robust version of the problem. We will prove that the robust maximum congested cut problem is coNP-Hard. Special cases solvable in polynomial time as well as approximation algorithms for some relevant hard cases will be proposed. The specialization of the proposed approaches to the well-studied class of Hose models (1999) will be discussed. Then, in the second part of the paper, we will investigate the case in which k commodities are given, and a maximum congested cut has to be computed in such a multicommodity flow context. This problem is NP-Hard. Some algorithmic considerations will be formulated in order to approximate the maximum congested cut in multicommodity networks, also addressing the robust version of the problem. A consequence of the stated results is a polynomial time algorithm for the sparsest cut problem in undirected graphs, for the special case in which k is O(log n), and an O(k/log n)-approximation algorithm for the general case, where n denotes the cardinality of the node set. Furthermore, a new heuristic approach for the directed sparsest cut problem will be suggested.
