Problema do Subgrafo Gerador Balanceado Máximo: desigualdades válidas e estratégias de branch-and-cut

Grafos de sinais modelam relações positivas/negativas entre elementos de um conjunto em diversos contextos. Essas situações frequentemente levam a estruturas desbalanceadas, ou seja, grafos cujos vértices não podem ser biparticionados de modo que as arestas positivas sejam aquelas dentro de uma partição. O problema do Subgrafo Gerador Balanceado Máximo busca encontrar um subgrafo gerador balanceado, com o maior número de arestas, de um grafo de sinais. Neste trabalho, buscamos fortalecer uma formulação existente com novas desigualdades válidas induzidas por cliques e avaliamos, via experimentos com estratégias de branch-and-cut, em que tipos de instância elas podem melhorar a eficiência do modelo