{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:02:04Z","timestamp":1757617324132,"version":"3.44.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s10107-024-02166-0","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T04:46:22Z","timestamp":1733805982000},"page":"1169-1209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On rank-monotone graph operations and minimal obstruction graphs for the Lov\u00e1sz\u2013Schrijver SDP hierarchy"],"prefix":"10.1007","volume":"213","author":[{"given":"Yu Hin","family":"Au","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Levent","family":"Tun\u00e7el","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,10]]},"reference":[{"issue":"part 2","key":"2166_CR1","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.dam.2012.07.012","volume":"164","author":"NE Aguilera","year":"2014","unstructured":"Aguilera, N.E., Escalante, M.S., Fekete, P.G.: On the facets of lift-and-project relaxations under graph operations. Discrete Appl. Math. 164(part 2), 360\u2013372 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2166_CR2","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/130950173","volume":"30","author":"YH Au","year":"2016","unstructured":"Au, Y.H., Tun\u00e7el, L.: A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1), 411\u2013451 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"2166_CR3","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.disopt.2017.10.001","volume":"27","author":"YH Au","year":"2018","unstructured":"Au, Y.H., Tun\u00e7el, L.: Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators. Discrete Optim. 27, 103\u2013129 (2018)","journal-title":"Discrete Optim."},{"key":"2166_CR4","doi-asserted-by":"crossref","unstructured":"Au, Y.H., Tun\u00e7el, L.: Stable set polytopes with high lift-and-project ranks for the Lov\u00e1sz\u2013Schrijver SDP operator. Math. Program. (2024)","DOI":"10.1007\/s10107-024-02093-0"},{"key":"2166_CR5","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.endm.2013.10.053","volume":"44","author":"SM Bianchi","year":"2013","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Tun\u00e7el, L.: Lov\u00e1sz\u2013Schrijver SDP-operator and a superclass of near-perfect graphs. Electron. Not. Discrete Math. 44, 339\u2013344 (2013)","journal-title":"Electron. Not. Discrete Math."},{"key":"2166_CR6","doi-asserted-by":"crossref","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Tun\u00e7el, L.: Lov\u00e1sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs. Math. Program. 162(1-2, Ser. A), 201\u2013223 (2017)","DOI":"10.1007\/s10107-016-1035-1"},{"key":"2166_CR7","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.dam.2023.01.012","volume":"332","author":"SM Bianchi","year":"2023","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Wagler, A.K.: Lov\u00e1sz\u2013Schrijver PSD-operator and the stable set polytope of claw-free graphs. Discrete Appl. Math. 332, 70\u201386 (2023)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2166_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/S1052623402420346","volume":"15","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0\u20131 integer programming. SIAM J. Optim. 15(1), 63\u201395 (2004)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2166_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. (2) 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math. (2)"},{"issue":"4","key":"2166_CR10","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2166_CR11","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/s10107-015-0879-0","volume":"151","author":"C Dobre","year":"2015","unstructured":"Dobre, C., Vera, J.: Exploiting symmetry in copositive programs via semidefinite hierarchies. Math. Program. 151(2), 659\u2013680 (2015)","journal-title":"Math. Program."},{"issue":"6","key":"2166_CR12","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/j.orl.2005.10.008","volume":"34","author":"MS Escalante","year":"2006","unstructured":"Escalante, M.S., Montelar, M.S., Nasini, G.L.: Minimal $$N_+$$-rank graphs: progress on Lipt\u00e1k and Tun\u00e7el\u2019s conjecture. Oper. Res. Lett. 34(6), 639\u2013646 (2006)","journal-title":"Oper. Res. Lett."},{"key":"2166_CR13","doi-asserted-by":"crossref","unstructured":"Grant, M.C., Boyd, S.P.: Graph implementations for nonsmooth convex programs. In: Recent Advances in Learning and Control, Volume 371 of Lect. Notes Control Inf. Sci., pp. 95\u2013110. Springer, London (2008)","DOI":"10.1007\/978-1-84800-155-8_7"},{"key":"2166_CR14","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1 (2014). http:\/\/cvxr.com\/cvx"},{"issue":"4","key":"2166_CR15","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1137\/090746525","volume":"20","author":"J Gouveia","year":"2010","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Theta bodies for polynomial ideals. SIAM J. Optim. 20(4), 2097\u20132118 (2010)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2166_CR16","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4), 796\u2013815 (2001)","journal-title":"Math. Oper. Res."},{"key":"2166_CR17","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Combin. 1:Article 1, approx. 48 (1994)","DOI":"10.37236\/1193"},{"key":"2166_CR18","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer programming and combinatorial optimization (Utrecht, 2001), Volume 2081 of Lecture Notes in Comput. Sci., pp. 293\u2013303. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"key":"2166_CR19","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Tighter linear and semidefinite relaxations for max-cut based on the Lov\u00e1sz\u2013Schrijver lift-and-project procedure. SIAM J. Optim. 12(2), 345\u2013375 (2001\/02)","DOI":"10.1137\/S1052623400379371"},{"issue":"4","key":"2166_CR20","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2166_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"2166_CR22","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"2166_CR23","doi-asserted-by":"crossref","unstructured":"Lipt\u00e1k, L., Tun\u00e7el, L.: The stable set problem and the lift-and-project ranks of graphs. Math. Program. 98(1\u20133, Ser. B), 319\u2013353 (2003). Integer programming (Pittsburgh, PA, 2002)","DOI":"10.1007\/s10107-003-0407-5"},{"issue":"2","key":"2166_CR24","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1287\/moor.2022.1290","volume":"48","author":"M Laurent","year":"2023","unstructured":"Laurent, M., Vargas, L.F.: Exactness of Parrilo\u2019s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph. Math. Oper. Res. 48(2), 1017\u20131043 (2023)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2166_CR25","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/05064401X","volume":"18","author":"J Pe\u00f1a","year":"2007","unstructured":"Pe\u00f1a, J., Vera, J., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1), 87\u2013105 (2007)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2166_CR26","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"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 Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"2166_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen, T., Tun\u00e7el, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"key":"2166_CR28","doi-asserted-by":"crossref","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11\/12(1\u20134), 625\u2013653 (1999). Interior point methods","DOI":"10.1080\/10556789908805766"},{"key":"2166_CR29","unstructured":"Vargas, L.F.: Sum-of-squares representations for copositive matrices and independent sets in graphs. PhD thesis, Tilburg University (2023)"},{"key":"2166_CR30","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.dam.2019.07.017","volume":"308","author":"AK Wagler","year":"2022","unstructured":"Wagler, A.K.: On the Lov\u00e1sz\u2013Schrijver PSD-operator on graph classes defined by clique cutsets. Discrete Appl. Math. 308, 209\u2013219 (2022)","journal-title":"Discrete Appl. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02166-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02166-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02166-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T01:47:01Z","timestamp":1757123221000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02166-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["2166"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02166-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"2 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}