Signed graphs, where edges are labeled as positive or negative, provide a natural framework for modeling compatibility and conflict. A signed graph is k-balanced when its vertices can be partitioned into k groups such that positive edges lie within groups and negative edges lie across them. We introduce the Competitive Groups Formation Problem, which seeks a maximum weighted k-balanced induced subgraph of a vertex-weighted, vertex-labeled signed graph, subject to label demand constraints within each group. This problem models several applications involving structural balance and constrained clustering. We develop an Integer Linear Programming formulation and propose several families of valid inequalities derived through an edge-contraction operation. Extensive computational experiments on synthetic and benchmark instances demonstrate that these inequalities significantly tighten the formulation and lead to substantial performance gains.

