Caracterizando facetas do politopo do Subgrafo Gerador Balanceado Máximo via comutação

• Natália Coelho UFC
• Manoel Campêlo UFC

DOI: https://doi.org/10.5753/etc.2026.23033

Resumo

Analisamos o politopo associado a uma formulação para o problema do Subgrafo Gerador Balanceado Máximo em grafos de sinais. Demonstramos a correspondência entre facetas induzidas por um subgrafo de sinais e suas comutações (i.e., grafos obtidos pela inversão dos sinais de qualquer corte de arestas do grafo). Utilizamos dessa propriedade para demonstrar desigualdades válidas indutoras de faceta nesse politopo.

Referências

Aref, S., Mason, A. J., and Wilson, M. C. (2020). A modeling and computational study of the frustration index in signed networks. Networks, 75(1):95–110.

Cartwright, D. and Harary, F. (1956). Structural balance: a generalization of heider’s theory. Psychological review, 63(5):277.

Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143–146.

Harary, F. (1959). On the measurement of structural balance. Behavioral Science, 4(4):316–323.

Zaslavsky, T. (1982). Signed graphs. Discrete Applied Mathematics, 4(1):47–74.