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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2011
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| Sumario: | 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. |
|---|---|
| Bibliografía: | Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T., Greedily Finding Dense Subgraphs (2000) Journal of Algorithms, 34, pp. 203-221 Asahiro, Y., Hassin, R., Iwama, K., Complexity of finding dense subgraphs (2002) Discrete Applied Mathematics, 121, pp. 15-26 Billionnet, A., Different formulations for solving the heaviest k-subgraph problem (2005) Information Systems and Operational Research, 43 (3), pp. 171-186 Feige, U., Kortsarz, G., Peleg, D., The Dense k-Subgraph Problem (2001) Algorithmica, 29, pp. 410-421 Han, Q., Ye, T., Zhang, J., Approximation of Dense-k-Subgraph, Working Paper, Department of Management Sciences (2000), Henry B. Tippie College of Business, The University of Iowa; Roupin, F., Billionnet, A., A deterministic approximation algorithm for the Densest k-Subgraph Problem (2008) International Journal of Operational Research, 3 (3), pp. 301-314 Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N., A polyhedral study of the maximum edge subgraph problem (2009) Electronic Notes in Discrete Mathematics, 35, pp. 197-202 Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N., A polyhedral study of the maximum edge subgraph problem, Submitted to Discrete Applied Mathematics |
| ISSN: | 15710653 |
| DOI: | 10.1016/j.endm.2011.05.052 |