{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:33:45Z","timestamp":1740123225529,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A linear description of the stable set polytope <jats:italic>STAB<\/jats:italic>(<jats:italic>G<\/jats:italic>) of a quasi-line graph <jats:italic>G<\/jats:italic> is given in Eisenbrand et al. (Combinatorica 28(1):45\u201367, 2008), where the so called Ben Rebea Theorem (Oriolo in Discrete Appl Math 132(3):185\u2013201, 2003) is proved. Such a theorem establishes that, for quasi-line graphs, <jats:italic>STAB<\/jats:italic>(<jats:italic>G<\/jats:italic>) is completely described by non-negativity constraints, clique inequalities, and clique family inequalities (CFIs). As quasi-line graphs are a superclass of line graphs, Ben Rebea Theorem can be seen as a generalization of Edmonds\u2019 characterization of the matching polytope (Edmonds in J Res Natl Bureau Stand B 69:125\u2013130, 1965), showing that the matching polytope can be described by non-negativity constraints, degree constraints and odd-set inequalities. Unfortunately, the description given by the Ben Rebea Theorem is not minimal, i.e., it is not known which are the (non-rank) clique family inequalities that are facet defining for <jats:italic>STAB<\/jats:italic>(<jats:italic>G<\/jats:italic>). To the contrary, it would be highly desirable to have a minimal description of <jats:italic>STAB<\/jats:italic>(<jats:italic>G<\/jats:italic>), pairing that of Edmonds and Pulleyblank (in: Berge, Chuadhuri (eds) Hypergraph seminar, pp 214\u2013242, 1974) for the matching polytope. In this paper, we start the investigation of a minimal linear description for the stable set polytope of quasi-line graphs. We focus on circular interval graphs, a subclass of quasi-line graphs that is central in the proof of the Ben Rebea Theorem. For this class of graphs, we move an important step forward, showing some strong sufficient conditions for a CFI to induce a facet of <jats:italic>STAB<\/jats:italic>(<jats:italic>G<\/jats:italic>). In particular, such conditions come out to be related to the existence of certain proper circulant graphs as subgraphs of <jats:italic>G<\/jats:italic>. These results allows us to settle two conjectures on the structure of facet defining inequalities of the stable set polytope of circulant graphs (P\u00eacher and Wagler in Math Program 105:311\u2013328, 2006) and of (fuzzy) circular graphs (Oriolo and Stauffer in Math Program 115:291\u2013317, 2008), and to slightly refine the Ben Rebea Theorem itself.\n<\/jats:p>","DOI":"10.1007\/s10479-021-04449-7","type":"journal-article","created":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T16:02:54Z","timestamp":1646323374000},"page":"1007-1029","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the facets of stable set polytopes of circular interval graphs"],"prefix":"10.1007","volume":"312","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2028-7005","authenticated-orcid":false,"given":"Gianpaolo","family":"Oriolo","sequence":"first","affiliation":[]},{"given":"Gautier","family":"Stauffer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"4449_CR1","volume-title":"Graphs and hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge, C. (1973). Graphs and hypergraphs. Paris: Dunod."},{"key":"4449_CR2","unstructured":"Bianchi, S., Nasini, G., Tolomei, P., & Torres, L. (2017). On dominating set polyhedra of circular interval graphs. Technical report."},{"key":"4449_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J. (1965). Maximum matching and a polyhedron with (0,1) vertices. Journal of Research of the National Bureau of Standards B, 69, 125\u2013130.","journal-title":"Journal of Research of the National Bureau of Standards B"},{"key":"4449_CR4","doi-asserted-by":"crossref","unstructured":"Edmonds, J., & Pulleyblank, W. (1974). Facets of 1-matching polyhedra. In Berge, C., & Chuadhuri, D. (eds.), Hypergraph seminar (pp. 214\u2013242).","DOI":"10.1007\/BFb0066196"},{"issue":"1","key":"4449_CR5","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00493-008-2244-x","volume":"28","author":"F Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Oriolo, G., Stauffer, G., & Ventura, P. (2008). The stable set polytope of quasi-line graphs. Combinatorica, 28(1), 45\u201367.","journal-title":"Combinatorica"},{"key":"4449_CR6","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., & Stauffer, G. (2014). Solving the weighted stable set problem in claw-free graphs via decomposition. Journal of ACM, 61(4):20:1\u201320:41.","DOI":"10.1145\/2629600"},{"key":"4449_CR7","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G., & Ventura, P. (2011). Stable sets in claw-free graphs: A journey through algorithms and polytopes. In Majhoub, R. (ed.), Progess in combinatorial optimization."},{"key":"4449_CR8","doi-asserted-by":"crossref","unstructured":"Galluccio, A., Gentile, C., & Ventura, P. (2014a). The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are w-perfect. Journal of Combinatorial Theory, Series B, 107, 92\u2013122.","DOI":"10.1016\/j.jctb.2014.02.006"},{"key":"4449_CR9","doi-asserted-by":"crossref","unstructured":"Galluccio, A., Gentile, C., & Ventura, P. (2014b). The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are GG-perfect. Journal of Combinatorial Theory, Series B, 108, 1\u201328.","DOI":"10.1016\/j.jctb.2014.02.009"},{"key":"4449_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1996.1715","volume":"69","author":"A Galluccio","year":"1997","unstructured":"Galluccio, A., & Sassano, A. (1997). The rank facets of the stable set polytope for claw-free graphs. Journal on Combinatorial Theory, 69, 1\u201338.","journal-title":"Journal on Combinatorial Theory"},{"key":"4449_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0095-8956(81)90033-2","volume":"31","author":"R Giles","year":"1981","unstructured":"Giles, R., & Trotter, L. E. J. (1981). On stable set polyhedra for $$k_{(1,3)}$$-free graphs. Journal on Combinatorial Theory, 31, 313\u2013326.","journal-title":"Journal on Combinatorial Theory"},{"key":"4449_CR12","doi-asserted-by":"crossref","unstructured":"Liebling, T.M., Oriolo, G., Spille, B., & Stauffer, G. (2004). On the non-rank facets of the stable set polytope of claw-free graphs and circulant graphs. Mathematical Methods of Operations Research, 59.","DOI":"10.1007\/s001860300317"},{"key":"4449_CR13","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., & Plummer, M. (1986). Matching theory. Amsterdam: North Holland."},{"key":"4449_CR14","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G. J. (1980). On maximal independent sets of vertices in claw-free graphs. Journal on Combinatorial Theory, 28, 284\u2013304.","journal-title":"Journal on Combinatorial Theory"},{"key":"4449_CR15","doi-asserted-by":"crossref","unstructured":"Nakamura, D., & Tamura, A. (2001). A revision of Minty\u2019s algorithm for finding a maximum weighted stable set of a claw-free graph. Journal of the Operations Research Society of Japan, 44(2), 194\u20132004.","DOI":"10.15807\/jorsj.44.194"},{"key":"4449_CR16","doi-asserted-by":"crossref","unstructured":"Nobili, P., & Sassano, A. (2015). An $${{\\cal{O}}}(n^2)$$-algorithm for the weighted stable set problem in claw-free graphs. CoRR\narXiv:1501.05775.","DOI":"10.1016\/j.dam.2013.10.015"},{"issue":"3","key":"4449_CR17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0166-218X(03)00400-1","volume":"132","author":"G Oriolo","year":"2003","unstructured":"Oriolo, G. (2003). Clique family inequalities for the stable set polytope for quasi-line graphs. Discrete Applied Mathematics, 132(3), 185\u2013201.","journal-title":"Discrete Applied Mathematics"},{"key":"4449_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10107-007-0176-7","volume":"115","author":"G Oriolo","year":"2008","unstructured":"Oriolo, G., & Stauffer, G. (2008). Clique-circulants and the stable set polytope of fuzzy circular interval graphs. Mathematical Programming, 115, 291\u2013317.","journal-title":"Mathematical Programming"},{"key":"4449_CR19","first-page":"1","volume":"86","author":"G Oriolo","year":"2011","unstructured":"Oriolo, G., Stauffer, G., & Ventura, P. (2011). Stable set in claw-free graphs: recent achievement and future challenges. Optima, 86, 1\u20138.","journal-title":"Optima"},{"key":"4449_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M Padberg","year":"1973","unstructured":"Padberg, M. (1973). On the facial structure of set packing polyhedra. Mathematical Programming, 5, 199\u2013215.","journal-title":"Mathematical Programming"},{"key":"4449_CR21","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10107-005-0655-7","volume":"105","author":"A P\u00eacher","year":"2006","unstructured":"P\u00eacher, A., & Wagler, A. (2006). Almost all webs are not rank-perfect. Mathematical Programming, 105, 311\u2013328.","journal-title":"Mathematical Programming"},{"key":"4449_CR22","doi-asserted-by":"crossref","unstructured":"Sbihi, N. (1980). Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Mathematics, 29, 53\u201376.","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"4449_CR23","unstructured":"Seb\u00f2, A. (2004). Minmax relations in cyclically ordered graphs. Laboratoire Leibniz, Grenoble: Technical report."},{"issue":"3","key":"4449_CR24","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.orl.2011.02.009","volume":"39","author":"G Stauffer","year":"2011","unstructured":"Stauffer, G. (2011). On the facets of the stable set polytope of quasi-line graphs. Operations Research Letters, 39(3), 208\u2013212.","journal-title":"Operations Research Letters"},{"key":"4449_CR25","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.orl.2011.02.009","volume":"39","author":"G Stauffer","year":"2011","unstructured":"Stauffer, G. (2011). The strongly minimal facets of the stable set polytope of quasi-line graphs. Operations Research Letters, 39, 208\u2013212.","journal-title":"Operations Research Letters"},{"key":"4449_CR26","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"L Trotter","year":"1975","unstructured":"Trotter, L. (1975). A class of facet producing graphs for vertex packing polyhedra. Discrete Mathematics, 12, 373\u2013388.","journal-title":"Discrete Mathematics"},{"key":"4449_CR27","doi-asserted-by":"crossref","unstructured":"Wagler, A. K. (2004). 7. Relaxing Perfectness: Which Graphs Are \u201cAlmost\u201d Perfect?, chapter\u00a07, pages 77\u201396. SIAM.","DOI":"10.1137\/1.9780898718805.ch7"},{"key":"4449_CR28","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/BF01609032","volume":"15","author":"E Zemel","year":"1978","unstructured":"Zemel, E. (1978). Lifting the facets of zero-one polytopes. Mathematical Programming, 15, 268\u2013277.","journal-title":"Mathematical Programming"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04449-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04449-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04449-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T15:35:03Z","timestamp":1658417703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04449-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,3]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["4449"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04449-7","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2022,3,3]]},"assertion":[{"value":"12 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}