A class of web-based facets for the generalized vertex packing problem

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

The generalized vertex packing problem seeks to identify a largest subset of nodes from an undirected graph, such that the subgraph induced by this subset of nodes contains no more than some threshold number of edges. This paper derives a class of valid inequalities based on certain special subgraphs called webs, which are general structures that subsume cliques, matchings, odd holes, and odd anti-holes. We also provide a set of conditions for this class of valid inequalities to be facet-inducing for the web subgraph polytope. Finally, we prescribe a web subgraph identification procedure, and test the computational benefits obtained by solving generalized vertex packing instances with formulations augmented by these web-based valid inequalities.

Original languageEnglish (US)
Pages (from-to)273-286
Number of pages14
JournalDiscrete Applied Mathematics
Volume146
Issue number3
DOIs
StatePublished - Mar 15 2005
Externally publishedYes

Keywords

  • Generalized vertex packing
  • Mixed-integer programming
  • Valid inequality
  • Web graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A class of web-based facets for the generalized vertex packing problem'. Together they form a unique fingerprint.

  • Cite this