## 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 language | English (US) |
---|---|

Pages (from-to) | 273-286 |

Number of pages | 14 |

Journal | Discrete Applied Mathematics |

Volume | 146 |

Issue number | 3 |

DOIs | |

State | Published - Mar 15 2005 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics