The stable set problem: some structural properties and relaxations

Given a graph, the edge formulation of the stable set problem is defined by two-variable constraints, one for each edge, expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine simplex pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. Between all possible pivots, we characterize degenerate and non-degenerate ones, and we differentiate those leading to an integer or to a fractional vertex. The graphic characterization of bases is crucial to prove another structural property of the fractional stable set polytope, concerning the adjacency of its vertices. In particular, we extend a necessary and sufficient condition due to Chvátal for adjacency of (integer) vertices of the stable set polytope to arbitrary (and possibly fractional) vertices of the fractional stable set polytope. These results lead us to prove that the Hirsch Conjecture is true for the fractional stable set polytope, i.e. the combinatorial diameter of this fractional polytope is at most equal to the number of edges of the given graph. We actually refine this bound in the non-bipartite case by proving a tighter bound, equal to the number of nodes of the graph. We also design a simplex-like algorithm for the stable set problem that relies on the adjacency properties mentioned above. Our algorithm generates only integer solutions without using cutting plane methods. Preliminary results are encouraging but show that cycling can occur, due to the high degree of degeneracy of the polytope. Nevertheless, the perspective of an exact combinatorial method of solution for the stable set problem based on this algorithm seems intriguing, provided that an anti-cycling rule is embedded in its current design. The graphic characterization of bases also provides a significant assessment on strength of different corner relaxations for the edge formulation of the Maximum Cardinality Stable Set Problem. The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical study of the strength of the corner and other related relaxations on benchmark problems. We validate with theoretical arguments the empirical results obtained by Fischetti and Monaci: we give a precise characterization of the bounds given by the corner relaxation and three of its extensions in the special case of the edge formulation of the stable set problem, for which a full description of the corner polyhedron is available. Our theoretical analysis shows that degeneracy plays a major role, as the difference in the bounds given by corner relaxations from two different optimal bases can be significantly large. Therefore, exploiting multiple degenerate bases for cut generation could give better bounds than working with just a single basis. Finally, a concave reformulation for Set Covering problems is presented, where integrality constraints are dropped and the original linear objective function is replaced by a concave one, penalizing fractional values. For such reformulation, any integer local optimum corresponds to a heuristic solution of the original problem. To determine local optima of our concave reformulation, we apply the Frank-Wolfe algorithm with a multi-start approach. The choice of a suitable parametric concave function allows us to regulate the smoothness of the objective function and to achieve sparseness of the local optimum. When applied to the edge formulation of the stable set problem, additional properties of local optima can be established. Namely, if the parameter of the objective function belongs to a certain range, binary valued variables of the local optimum can be fixed, allowing a reduction of the dimension of the problem. Computational experiments show that the concave heuristic is effective on some difficult benchmark problems.