TY - GEN
T1 - Persistency of Linear Programming Relaxations for the Stable Set Problem
AU - Rodríguez-Heck, Elisabeth
AU - Stickler, Karl
AU - Walter, Matthias
AU - Weltge, Stefan
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.
AB - The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.
KW - Integer linear programming
KW - Persistency
KW - Stable set
UR - http://www.scopus.com/inward/record.url?scp=85083970484&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-45771-6_27
DO - 10.1007/978-3-030-45771-6_27
M3 - Conference contribution
AN - SCOPUS:85083970484
SN - 9783030457709
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 351
EP - 363
BT - Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
A2 - Bienstock, Daniel
A2 - Zambelli, Giacomo
PB - Springer
T2 - 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Y2 - 8 June 2020 through 10 June 2020
ER -