Abstract
A polytope \(P\subset [0,1]^n\) is said to have the persistency property if for every vector \(c\in \mathbb {R}^{n}\) and every c-optimal point \(x\in P\), there exists a c-optimal integer point \(y\in P\cap \{0,1\}^n\) such that \(x_i = y_i\) for each \(i \in \{1,\dots ,n\}\) with \(x_i \in \{0,1\}\). In this paper, we consider a relaxation of the persistency property, called 1-persistency, over the clique relaxation of the stable set polytope in graphs. In particular, we study the family \(\mathcal {Q}\) of graphs whose clique relaxation of the stable set polytope has 1-persistency. The main objective of this contribution is to analyze forbidden structures for a given graph to belong to \(\mathcal {Q}\). The graphs given by these structures are denoted here as \(\mathrm {mn\mathcal {Q}}\). On one hand, we provide sufficient conditions for a graph to belong to \(\mathcal {Q}\), and identify several graph classes of this family. On the other hand, we give two different infinite families of forbidden minimal structures for this class of graphs. We conclude the paper by suggesting an interesting future line of work about the persistency-preservation property of valid inequalities and its potential practical applications.
Partially supported by grant PIP0227 - CONICET and grant PICT 3032-ANPCyT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chudnovski, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51–229 (2006)
Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18(2), 138–154 (1975)
Koster, A., Wagler, A.: The extreme points of QSTAB(G) and its implications, ZIB-Report 06-30 (2006)
Nemhauser, G., Trotter, L.: Vertex packings: structural properties and algorithms. Math. Prog. 8(1), 232–248 (1975)
Rodríguez-Heck, E., Stickler, K., Walter, M., Weltge, S.: Persistency of linear programming relaxations for the stable set problem. Math. Prog. 192, 387–407 (2022)
Wagler, A.K.: Rank-perfect and weakly rank-perfect graphs. Math. Meth. Oper. Res. 56, 127–149 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Delle Donne, D., Escalante, M., Fekete, P., Moroni, L. (2024). 1-Persistency of the Clique Relaxation of the Stable Set Polytope. In: Basu, A., Mahjoub, A.R., Salazar González, J.J. (eds) Combinatorial Optimization. ISCO 2024. Lecture Notes in Computer Science, vol 14594. Springer, Cham. https://doi.org/10.1007/978-3-031-60924-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-60924-4_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60923-7
Online ISBN: 978-3-031-60924-4
eBook Packages: Computer ScienceComputer Science (R0)