Journal articles
Year
2026
Abstract
A polytope PPP is said to have the persistency property if for every vector ccc and every LPLPLP-optimal point x∗x^*x∗, there exists a IPIPIP-optimal integer point xxx such that xi=xi∗x_i = x^*_ixi=xi∗ for each iii with xi∗x^*_ixi∗ integer.
In this paper, we consider a relaxation of the persistency property called 1-persistency. We study the family F\mathcal{F}F of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as F\mathcal{F}F-persistent graphs. We provide sufficient conditions for a graph to be F\mathcal{F}F-persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of kkk-umbrella graphs, and study which of them belong to F\mathcal{F}F. The property of being F\mathcal{F}F-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family F\mathcal{F}F, i.e., minimally not F\mathcal{F}F-persistent (mnF\mathcal{F}F) graphs. In this line, we identify some mnF\mathcal{F}F-umbrella graphs and also other forbidden minimal structures for F\mathcal{F}F-persistency outside this family (named as whale graphs).
DELLE DONNE, D., ESCALANTE, M., FEKETE, P. et MORONI, L. (2026). The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures. Discrete Applied Mathematics, 387(1), pp. 37-56.