First, we observe that SST cuts do not increase the computational complexity of solving a linear optimization problem over any polytope $P$. However, separating the integer hull of \(P\) enriched by SST cuts can be NP-hard, even if \(P\) is integral and has a compact formulation. We study this phenomenon more in-depth for the stable set problem, particularly for subclasses of perfect graphs. For bipartite graphs, we give a complete characterization of the integer hull after adding SST cuts based on odd-cycle inequalities. For trivially perfect graphs, we observe that the separation problem is still NP-hard after adding a generic set of SST cuts. Our main contribution is to identify a specific class of SST cuts, called stringent SST cuts, that keeps the separation problem polynomial and a complete set of inequalities, namely SST clique cuts, that yield a complete linear description.
We complement these results by giving SST cuts based presolving techniques and provide a computational study to compare the different approaches. In particular, our newly identified stringent SST cuts dominate other approaches.