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...
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco |
| Aporte de: |
| id |
todo:paper_15710653_v37_nC_p303_Marenco |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15710653_v37_nC_p303_Marenco2023-10-03T16:27:06Z Combinatorial properties and further facets of maximum edge subgraph polytopes Marenco, J. Saban, D. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, J. Saban, D. 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. |
| format |
JOUR |
| author |
Marenco, J. Saban, D. |
| author_facet |
Marenco, J. Saban, D. |
| author_sort |
Marenco, J. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco |
| work_keys_str_mv |
AT marencoj combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes AT saband combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes |
| _version_ |
1807323372980273152 |