A polyhedral study of the maximum edge subgraph problem

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 of finding a k-vertex subset such...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Marenco, Javier Leonardo, Sabán, Daniela, Stier Moses, Nicolás E.
Publicado:	2012
Materias:	Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral studies Polytopes Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2573_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0166218X_v160_n18_p2573_Bonomo
record_format	dspace
spelling	paper:paper_0166218X_v160_n18_p2573_Bonomo2025-07-30T17:54:23Z A polyhedral study of the maximum edge subgraph problem Bonomo, Flavia Marenco, Javier Leonardo Sabán, Daniela Stier Moses, Nicolás E. Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral combinatorics Polyhedral studies Polytopes Quasi-cliques Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity 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 of 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 in this work. © 2011 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Saban, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Stier-Moses, N.E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2573_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral combinatorics Polyhedral studies Polytopes Quasi-cliques Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity
spellingShingle	Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral combinatorics Polyhedral studies Polytopes Quasi-cliques Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity Bonomo, Flavia Marenco, Javier Leonardo Sabán, Daniela Stier Moses, Nicolás E. A polyhedral study of the maximum edge subgraph problem
topic_facet	Maximum edge subgraph problem Polyhedral combinatorics Quasi-cliques Branch-and-cut algorithms Computational studies Integer programming formulations Polyhedral approach Polyhedral combinatorics Polyhedral studies Polytopes Quasi-cliques Separation problems Social Network Analysis Subgraph problems Valid inequality Integer programming Linear programming Social networking (online) Computational complexity
description	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 of 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 in this work. © 2011 Elsevier B.V. All rights reserved.
author	Bonomo, Flavia Marenco, Javier Leonardo Sabán, Daniela Stier Moses, Nicolás E.
author_facet	Bonomo, Flavia Marenco, Javier Leonardo Sabán, Daniela Stier Moses, Nicolás E.
author_sort	Bonomo, Flavia
title	A polyhedral study of the maximum edge subgraph problem
title_short	A polyhedral study of the maximum edge subgraph problem
title_full	A polyhedral study of the maximum edge subgraph problem
title_fullStr	A polyhedral study of the maximum edge subgraph problem
title_full_unstemmed	A polyhedral study of the maximum edge subgraph problem
title_sort	polyhedral study of the maximum edge subgraph problem
publishDate	2012
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2573_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2573_Bonomo
work_keys_str_mv	AT bonomoflavia apolyhedralstudyofthemaximumedgesubgraphproblem AT marencojavierleonardo apolyhedralstudyofthemaximumedgesubgraphproblem AT sabandaniela apolyhedralstudyofthemaximumedgesubgraphproblem AT stiermosesnicolase apolyhedralstudyofthemaximumedgesubgraphproblem AT bonomoflavia polyhedralstudyofthemaximumedgesubgraphproblem AT marencojavierleonardo polyhedralstudyofthemaximumedgesubgraphproblem AT sabandaniela polyhedralstudyofthemaximumedgesubgraphproblem AT stiermosesnicolase polyhedralstudyofthemaximumedgesubgraphproblem
_version_	1840322699214192640

A polyhedral study of the maximum edge subgraph problem

Ejemplares similares