A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph

Rosa Figueiredo 1 Yuri Frota 2 Martine Labbé 3
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We are interested in the solution of the maximum k-balanced subgraph problem. Let G = (V, E, s) be a signed graph and k a positive scalar. A signed graph is k-balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k-balanced subgraph problem is the problem of finding a subgraph of G that is k-balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative vs conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work.
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01937015
Contributor : Martine Labbé <>
Submitted on : Tuesday, November 27, 2018 - 7:28:24 PM
Last modification on : Monday, July 15, 2019 - 10:29:48 PM

File

kBPSG_BW-DAM.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Rosa Figueiredo, Yuri Frota, Martine Labbé. A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph. Discrete Applied Mathematics, Elsevier, 2018, 261, pp.164-185. ⟨10.1016/j.dam.2018.11.022⟩. ⟨hal-01937015⟩

Share

Metrics

Record views

198

Files downloads

155