Combinatorial properties and further facets of maximum edge subgraph polytopes

Given a graph G and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset of G such that the number of edges within the subset is maximum. This NP-hard problem arises in the analysis of cohesive subgroups in social networks. In this work we study the polytope P(G,k) a...

Descripción completa

Detalles Bibliográficos
Autores principales: Marenco, Javier Leonardo, Sabán, Daniela
Publicado: 2011
Materias:
Diameter of polytopes
Facets
Maximum edge subgraph problem
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p303_Marenco
http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v37_nC_p303_Marenco
record_format dspace
spelling paper:paper_15710653_v37_nC_p303_Marenco2023-06-08T16:24:27Z Combinatorial properties and further facets of maximum edge subgraph polytopes Marenco, Javier Leonardo Sabán, Daniela Diameter of polytopes Facets Maximum edge subgraph problem Given a graph G and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset of G such that the number of edges within the subset is maximum. This NP-hard problem arises in the analysis of cohesive subgroups in social networks. In this work we study the polytope P(G,k) associated with a straightforward integer programming formulation of the maximum edge subgraph problem. We characterize the graph generated by P(G,k) and give a tight bound on its diameter. We give a complete description of P(K1n,k), where K1n is the star on n+1 vertices, and we conjecture a complete description of P(mK2,k), where mK2 is the graph composed by m disjoint edges. Finally, we introduce three families of facet-inducing inequalities for P(G,k), which generalize known families of valid inequalities for this polytope. © 2011 Elsevier B.V. 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p303_Marenco http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Diameter of polytopes
Facets
Maximum edge subgraph problem
spellingShingle Diameter of polytopes
Facets
Maximum edge subgraph problem
Marenco, Javier Leonardo
Sabán, Daniela
Combinatorial properties and further facets of maximum edge subgraph polytopes
topic_facet Diameter of polytopes
Facets
Maximum edge subgraph problem
description Given a graph G and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset of G such that the number of edges within the subset is maximum. This NP-hard problem arises in the analysis of cohesive subgroups in social networks. In this work we study the polytope P(G,k) associated with a straightforward integer programming formulation of the maximum edge subgraph problem. We characterize the graph generated by P(G,k) and give a tight bound on its diameter. We give a complete description of P(K1n,k), where K1n is the star on n+1 vertices, and we conjecture a complete description of P(mK2,k), where mK2 is the graph composed by m disjoint edges. Finally, we introduce three families of facet-inducing inequalities for P(G,k), which generalize known families of valid inequalities for this polytope. © 2011 Elsevier B.V.
author Marenco, Javier Leonardo
Sabán, Daniela
author_facet Marenco, Javier Leonardo
Sabán, Daniela
author_sort Marenco, Javier Leonardo
title Combinatorial properties and further facets of maximum edge subgraph polytopes
title_short Combinatorial properties and further facets of maximum edge subgraph polytopes
title_full Combinatorial properties and further facets of maximum edge subgraph polytopes
title_fullStr Combinatorial properties and further facets of maximum edge subgraph polytopes
title_full_unstemmed Combinatorial properties and further facets of maximum edge subgraph polytopes
title_sort combinatorial properties and further facets of maximum edge subgraph polytopes
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p303_Marenco
http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
work_keys_str_mv AT marencojavierleonardo combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes
AT sabandaniela combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes
_version_ 1768541578687676416

Ejemplares similares