Nicolás Stier-Moses

A polyhedral study of the maximum edge subgraph problem

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

Abstract:
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