Abstract.
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovász and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N 0 -, N-, or N + -rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N 0 - or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N + -ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N + -rank of a graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aguilera, N.E., Bianchi, S.M., Nasini, G.L.: Lift and project relaxations for the matching and related polytopes. manuscript 2002
Balas, E.: Disjunctive programming: Properties of the convex hull of feasible points. Management Science Research Report 348 GSIA, Carnegie Mellon University, Pittsburgh, PA, USA, 1974
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Prog. A 58, 295–323 (1993)
Chvátal, V.: On certain polytopes associated with graphs. J. of Combin. Theory Ser. B 18, 138–154 (1975)
Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26, 19–30 (2001)
Goemans, M.X., Tunçel, L.: When does the positive semidefiniteness constraint help in lifting procedures?. Math. Oper. Res. 26, 796–815 (2001)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization (Springer, New York, 1988)
Gerards, A.M.H., Schrijver, A.: Matrices with the Edmonds–Johnson property. Combinatorica 6, 365–379 (1986)
Kotlov, A., Lovász, L., Vempala, S.: The Colin de Verdière number and sphere representations of a graph. Combinatorica 17, 483–521 (1997)
Laurent, M.: Tight linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project technique. SIAM J. Optim. 12, 345–375 (2002)
Lipták, L.: Critical Facets of the Stable Set Polytope. Ph.D. Thesis, Yale University, 1999
Lipták, L., Lovász, L.: Critical facets of the stable set polytope. Combinatorica 21, 61–88 (2001)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1–7 (1979)
Lovász, L.: Combinatorial optimization: some problems and trends. DIMACS Tech. Report 92-53, NJ, USA, (1992)
Lovász, L.: Steinitz representations of polyhedra and the Colin de Verdière number. J. Combin. Theory Ser. B 82, 223–236 (2001)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166–190 (1991)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Mathematics 3, 411–430 (1990)
Stephen, T., Tunçel, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24, 1–7 (1999)
Wessel, W.: Kanten-kritische graphen mit der zusammenhangszahl 2. Manuscripta Math. 2, 309–334 (1970)
Wolsey, L.A.: Further facet generating procedures for vertex packing polytopes. Math. Prog. A 11, 158–163 (1976)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of these authors was supported in part by a PREA from Ontario, Canada and research grants from NSERC.
Mathematics Subject Classification (2000): 0C10, 90C22, 90C27, 47D20
Rights and permissions
About this article
Cite this article
Lipták, L., Tunçel, L. The stable set problem and the lift-and-project ranks of graphs. Math. Program., Ser. B 98, 319–353 (2003). https://doi.org/10.1007/s10107-003-0407-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0407-5