Name
Abstract | ||
|---|---|---|
Given an undirected graph G = (V, E) and a positive integer k is an element of {1, ..., vertical bar V vertical bar}, we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time. (C) 2021 The Author(s). Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.dam.2021.01.019 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Stable sets, Independent sets, Cardinality constraints, Combinatorial optimization, Integer programming, Graph classes | Journal | 303 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Phillippe Samer | 1 | 0 | 0.34 |
| Dag Haugland | 2 | 151 | 15.18 |