A polyhedral study of the maximum edge subgraph problem

BONOMO, FLAVIA; MARENCO, JAVIER; SABÁN, DANIELA; STIER MOSES, NICOLÁS

Gramado

Simposio; Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS); 2009

The study of cohesive subgroups is a relevant aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the definition of clique in a graph, one of them generating the maximum edge subgraph problem. Given a graph and an integer k, this problem consists in finding a k-vertex subset such that the number of edges within the subset is maximum. This problem is NP-hard, and in this work we start an integer programming approach by studying the polytope associated to a straightforward integer programming formulation. We present several families of facet-inducing valid inequalities for this polytope, and we discuss the separation problem associated to restrictions of some of these families.