A Polyhedral Study of the Maximum Edge Subgraph Problem

A Polyhedral Study of the Maximum Edge Subgraph Problem

By
Daniela Saban, Flavia Bonomo, Javier Marenco, Nicolas Stier-Moses
Electronic Notes in Discrete Mathematics. December
1, 2009, Vol. 35, Pages 197-202

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.