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

Abstract

A polytope P ⊂ [0, 1]n is said to have the persistency property if for every vector c ∈ Rn and every c-optimal point x ∈ P , thereexists a c-optimal integer point y ∈ P ∩ {0, 1}n such that xi = yi foreach i ∈ {1, . . . , n} with xi ∈ {0, 1}. In this paper, we consider a relaxation of the persistency property, called 1-persistency, over the cliquerelaxation of the stable set polytope in graphs. In particular, we studythe family Q of graphs whose clique relaxation of the stable set polytopehas 1-persistency. The main objective of this contribution is to analyzeforbidden structures for a given graph to belong to Q. The graphs givenby these structures are denoted here as mnQ. On one hand, we providesufficient conditions for a graph to belong to Q, and identify severalgraph classes of this family. On the other hand, we give two differentinfinite families of forbidden minimal structures for this class of graphs.We conclude the paper by suggesting an interesting future line of workabout the persistency-preservation property of valid inequalities and itspotential practical applications.