The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures

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, there exists a c-optimal integer point y ∈ P ∩ {0,1}n such that xi = yi for each i ∈ {1,...,n} with xi ∈ {0,1}. In this paper, we consider a relaxation of the persistency property called 1-persistency. We study the family Q of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as Q-persistent graphs. We provide sufficient conditions for a graph to be Q-persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of (k,U)-umbrella graphs, and study which of them belong to Q. The property of being Q-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family Q, i.e., minimally not Q-persistent (mnQ) graphs. In this line, we identify some mnQ (k,U)-umbrella graphs and also other forbidden minimal structures for Q-persistency outside this family (named as whale graphs).