In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0129 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0129 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We consider combinatorial optimization problems arising in radiation therapy. Given a matrix I with non‐negative integer entries, we seek a decomposition of I as a weighted sum of binary matrices having the consecutive ones property, such that the total sum of the coefficients is minimized. The coefficients are restricted to be non‐negative integers. Here, we investigate variants of the problem with additional constraints on the matrices used in the decomposition. Constraints appearing in the application include the interleaf motion and interleaf distance constraints. The former constraint was previously studied by Baatar et al. [Discr Appl Math 152 (2005), 6–34] and Kalinowski [Discr Appl Math 152 (2005), 52–88]. The latter constraint was independently considered by Kumar [Working paper (2007)] in the case where coefficients of the decomposition are not restricted to be integers. For both constraints, we prove that finding an optimal decomposition reduces to finding a maximum value potential in an auxiliary network with integer arc lengths and no negative length cycle. This allows us to simplify and unify the previous approaches. Moreover, we give an O ( MN + K M ) algorithm to solve the problem under the interleaf distance constraint, where M and N , respectively, denote the number of rows and columns of the matrix I and K is the number of matrices used in the decomposition. We also give an O ( MN log M + K M ) algorithm for solving the problem under the interleaf motion constraint and hence improve on previous results. Finally, we show the problem can still be solved in O ( MN log M + K M ) time when both constraints are considered simultaneously. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010