Persistency of Linear Programming Formulations for the Stable Set Problem

Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter, Stefan Weltge

    Research output: Working paper

    38 Downloads (Pure)


    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 is persistent as well. We show that any stronger LP formulation that satisfies mild conditions cannot be persistent on all graphs, unless it is always equal to the stable-set polytope.
    Original languageEnglish
    Publication statusPublished - 6 Nov 2019


    • cs.DM
    • math.CO
    • math.OC


    Dive into the research topics of 'Persistency of Linear Programming Formulations for the Stable Set Problem'. Together they form a unique fingerprint.

    Cite this