## 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