A polyhedral study of the maximum edge subgraph problem
BONOMO, FLAVIA; MARENCO, JAVIER; SABÁN, DANIELA; STIER-MOSES, NICOLÁS
DISCRETE APPLIED MATHEMATICS
ELSEVIER SCIENCE BV
Año: 2012 vol. 160 p. 2573 - 2590
The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented inthis work.