{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:29:06Z","timestamp":1773246546372,"version":"3.50.1"},"reference-count":20,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T00:00:00Z","timestamp":1570579200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,9,4]]},"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic>\u00a0=\u00a0(<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) be an undirected graph where the edges in <jats:italic>E<\/jats:italic> have non-negative weights. A star in <jats:italic>G<\/jats:italic> is either a single node of <jats:italic>G<\/jats:italic> or a subgraph of <jats:italic>G<\/jats:italic> where all the edges share one common end-node. A star forest is a collection of vertex-disjoint stars in <jats:italic>G<\/jats:italic>. The weight of a star forest is the sum of the weights of its edges. This paper deals with the problem of finding a Maximum Weight Spanning Star Forest (MWSFP) in <jats:italic>G<\/jats:italic>. This problem is <jats:italic>NP<\/jats:italic>-hard but can be solved in polynomial time when <jats:italic>G<\/jats:italic> is a cactus [Nguyen, <jats:italic>Discrete Math. Algorithms App.<\/jats:italic> <jats:bold>7<\/jats:bold> (2015) 1550018]. In this paper, we present a polyhedral investigation of the MWSFP. More precisely, we study the facial structure of the star forest polytope, denoted by <jats:italic>SFP<\/jats:italic>(<jats:italic>G<\/jats:italic>), which is the convex hull of the incidence vectors of the star forests of <jats:italic>G<\/jats:italic>. First, we prove several basic properties of <jats:italic>SFP<\/jats:italic>(<jats:italic>G<\/jats:italic>) and propose an integer programming formulation for MWSFP. Then, we give a class of facet-defining inequalities, called <jats:italic>M<\/jats:italic>-tree inequalities, for <jats:italic>SFP<\/jats:italic>(<jats:italic>G<\/jats:italic>). We show that for the case when <jats:italic>G<\/jats:italic> is a tree, the <jats:italic>M<\/jats:italic>-tree and the nonnegativity inequalities give a complete characterization of <jats:italic>SFP<\/jats:italic>(<jats:italic>G<\/jats:italic>). Finally, based on the description of the dominating set polytope on cycles given by Bouchakour <jats:italic>et al.<\/jats:italic> [<jats:italic>Eur. J. Combin.<\/jats:italic> <jats:bold>29<\/jats:bold> (2008) 652\u2013661], we give a complete linear description of <jats:italic>SFP<\/jats:italic>(<jats:italic>G<\/jats:italic>) when <jats:italic>G<\/jats:italic> is a cycle.<\/jats:p>","DOI":"10.1051\/ro\/2018076","type":"journal-article","created":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T18:48:29Z","timestamp":1536173309000},"page":"1763-1773","source":"Crossref","is-referenced-by-count":2,"title":["On the star forest polytope for trees and cycles"],"prefix":"10.1051","volume":"53","author":[{"given":"Meziane","family":"Aider","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lamia","family":"Aoudia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mourad","family":"Ba\u00efou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. Ridha","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2181-3847","authenticated-orcid":false,"given":"Viet Hung","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,10,9]]},"reference":[{"key":"R1","unstructured":"Agra A., Cardoso D., Cerfeira O. and Rocha E., A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (2005)."},{"key":"R2","unstructured":"Athanassopoulos S., Caragiannis I., Kaklamanis C. and Kyropoulou M., An improved approximation bound for spanning star forest and color saving. In: MFCS. Springer, Berlin, Heidelberg (2009) 90\u2013101."},{"key":"R3","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1137\/070706070","volume":"23","author":"Ba\u00efou","year":"2009","journal-title":"SIAM J. Discrete Math."},{"key":"R4","unstructured":"Ba\u00efou M., Barahona F., Simple extended formulation for the dominating set polytope via facility location, Tech. Rep. RC25325, IBM Research (2012)."},{"key":"R5","unstructured":"Ba\u00efou M., Barahona F., Algorithms for minimum weighted dominating sets in cycles and cacti, Tech. Rep. RC25488, IBM Research (2014)."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Ba\u00efou M. and Barahona F., The dominating set polytope via facility location. Combinatorial Optimization. ISCO 2014. In Vol. 8596 of Lecture Note Computer Sciences (2014) 38\u201349.","DOI":"10.1007\/978-3-319-14115-2_4"},{"key":"R7","unstructured":"Berry V., Guillemot S., Nicholas F. and Paul C., On the approximation of computing evolutionary trees. In: Proc. of the Eleventh Annual International Computing and Combinatorics Conference. Springer, Berlin, Heidelberg (2005) 115\u2013123."},{"key":"R8","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1016\/j.ejc.2007.03.010","volume":"29","author":"Bouchakour","year":"2008","journal-title":"Eur. J. Combin."},{"key":"R9","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0012-365X(96)00164-1","volume":"165\/166","author":"Bouchakour","year":"1997","journal-title":"Discrete Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"Bui-Xuan","year":"2011","journal-title":"Theoret. Comput. Sci."},{"key":"R11","unstructured":"Chakrabarty D. and Goel G., On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: FOCS \u201808. IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, 1975 (2008) 687\u2013696."},{"key":"R12","unstructured":"Chen N., Engelberg R., Nguyen C.T., Raghavendra P., Rudra A. and Singh G., Improved approximation algorithms for the spanning star forest problem. In: APPROX\/RANDOM In Vol. 4627 of Lecture Notes in Computer Science book series (2007) 44\u201358."},{"key":"R13","unstructured":"Haynes T.W., Slater P.J. and Hedetniemi S.T., Fundamentals of Domination in Graphs. CRC Press, Boca Raton, FL (1998)."},{"key":"R14","unstructured":"He J. and Liang H., On variants of the spanning star forest problem. In: Proc. of FAW-AAIM (2011) 70\u201381."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Ito T., Kakimura N., Kamiyama N., Kobayashi Y. and Okamoto Y., Minimum-cost b -edge dominating sets on trees. In, Vol. 8880 of Lecture Notes Computer Sciences (2014) 195\u2013207.","DOI":"10.1007\/978-3-319-13075-0_16"},{"key":"R16","first-page":"443","volume":"17","author":"Mahjoub","year":"1983","journal-title":"Annal. Discrete Math."},{"key":"R17","unstructured":"Nguyen C.T., Shen J., Hou M., Sheng L., Miller W. and Zhang L., Approximating the spanning star forest problem and its applications to genomic sequence alignment. In: Proc. of SODA (2007) 645\u2013654."},{"key":"R18","doi-asserted-by":"crossref","first-page":"1550018","DOI":"10.1142\/S1793830915500184","volume":"7","author":"Nguyen","year":"2015","journal-title":"Discrete Math. Algorithms App."},{"key":"R19","unstructured":"Saxena A., Some results on the dominating set polytope of a cycle. Technical Report CMU (2004)."},{"key":"R20","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018076\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T18:58:21Z","timestamp":1598641101000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,9]]},"references-count":20,"journal-issue":{"issue":"5"},"alternative-id":["ro151119"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018076","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,9]]}}}