Nicolás Stier-Moses

A polyhedral study of the maximum edge subgraph problem

Coauthor(s): Flavia Bonomo, J. Marenco, Daniela Saban.

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.

Source: Discrete Applied Mathematics
Exact Citation:
Bonomo, Flavia, J. Marenco, Daniela Saban, and Nicolás Stier-Moses. "A polyhedral study of the maximum edge subgraph problem." Discrete Applied Mathematics (forthcoming).
Date: 2012