1-Persistency of the Clique Relaxation of the Stable Set Polytope

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.