Maximum Balanced Spanning Subgraph Problem: Valid Inequalities and Branch-and-Cut Strategies

Signed graphs model positive/negative relationships between elements of a set in various contexts. These situations often lead to unbalanced structures, that is, graphs whose vertices cannot be bipartitioned in such a way that the positive edges are those within a partition. The Maximum Balanced Spanning Subgraph problem seeks to find a balanced spanning subgraph, with the largest number of edges, in a signed graph. In this work, we aim to strengthen an existing formulation with new valid inequalities induced by cliques, and we evaluate, through experiments using branch-and-cut strategies, on which types of instances they can improve the model's efficiency.