Pablo G. Fekete

dblp:04/9926 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
2since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 since 2021Artificial intelligence and machine learning · 1 · 1 since 2021
YearPublicationVenuePosition
2026 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 ∈ R n and every c -optimal point x ∈ P , there exists a c -optimal integer point y ∈ P ∩ { 0 , 1 } n such that x i = y i for each i ∈ { 1 , … , n } with x i ∈ { 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 (mn Q ) graphs. In this line, we identify some mn Q ( k , U ) -umbrella graphs and also other forbidden minimal structures for Q -persistency outside this family (named as whale graphs).
Diego Delle Donne, Mariana S. Escalante, Pablo G. Fekete, Lucía Moroni
Discret. Appl. Math.3
2024 1-Persistency of the Clique Relaxation of the Stable Set Polytope
Diego Delle Donne, Mariana S. Escalante, Pablo G. Fekete, Lucía Moroni
ISCO3
2014 On the facets of lift-and-project relaxations under graph operations
Néstor E. Aguilera, Mariana S. Escalante, Pablo G. Fekete
Discret. Appl. Math.3