Let G = (V, E) be an undirected graph where the edges in E have non-negative weights. A star in G is either a single node of G or a subgraph of G where all the edges share one common end-node. A star forest is a collection of vertex-disjoint stars in G. 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 G. This problem is NP-hard but can be solved in polynomial time when G is a cactus [Nguyen, Discrete Math. Algorithms App. 7 (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 SFP(G), which is the convex hull of the incidence vectors of the star forests of G. First, we prove several basic properties of SFP(G) and propose an integer programming formulation for MWSFP. Then, we give a class of facet-defining inequalities, called M-tree inequalities, for SFP(G). We show that for the case when G is a tree, the M-tree and the nonnegativity inequalities give a complete characterization of SFP(G). Finally, based on the description of the dominating set polytope on cycles given by Bouchakour et al. [Eur. J. Combin. 29 (2008) 652–661], we give a complete linear description of SFP(G) when G is a cycle.
Accepté le :
DOI : 10.1051/ro/2018076
Mots-clés : Combinatorial optimization, polyhedral combinatorics, star forest, facility location, dominating set
@article{RO_2019__53_5_1763_0,
author = {Aider, Meziane and Aoudia, Lamia and Ba{\"\i}ou, Mourad and Mahjoub, A. Ridha and Nguyen, Viet Hung},
title = {On the star forest polytope for trees and cycles},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1763--1773},
publisher = {EDP-Sciences},
volume = {53},
number = {5},
year = {2019},
doi = {10.1051/ro/2018076},
mrnumber = {4016522},
zbl = {1434.90162},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018076/}
}
TY - JOUR AU - Aider, Meziane AU - Aoudia, Lamia AU - Baïou, Mourad AU - Mahjoub, A. Ridha AU - Nguyen, Viet Hung TI - On the star forest polytope for trees and cycles JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1763 EP - 1773 VL - 53 IS - 5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018076/ DO - 10.1051/ro/2018076 LA - en ID - RO_2019__53_5_1763_0 ER -
%0 Journal Article %A Aider, Meziane %A Aoudia, Lamia %A Baïou, Mourad %A Mahjoub, A. Ridha %A Nguyen, Viet Hung %T On the star forest polytope for trees and cycles %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1763-1773 %V 53 %N 5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018076/ %R 10.1051/ro/2018076 %G en %F RO_2019__53_5_1763_0
Aider, Meziane; Aoudia, Lamia; Baïou, Mourad; Mahjoub, A. Ridha; Nguyen, Viet Hung. On the star forest polytope for trees and cycles. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1763-1773. doi : 10.1051/ro/2018076. http://www.numdam.org/articles/10.1051/ro/2018076/
, , and , A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (2005).
, , and , An improved approximation bound for spanning star forest and color saving. In: MFCS. Springer, Berlin, Heidelberg (2009) 90–101. | MR | Zbl
and , On the integrality of some facility location polytopes. SIAM J. Discrete Math. 23 (2009) 665–679. | DOI | MR | Zbl
, , Simple extended formulation for the dominating set polytope via facility location, Tech. Rep. RC25325, IBM Research (2012).
, , Algorithms for minimum weighted dominating sets in cycles and cacti, Tech. Rep. RC25488, IBM Research (2014).
and , The dominating set polytope via facility location. Combinatorial Optimization. ISCO 2014. In Vol. 8596 of Lecture Note Computer Sciences (2014) 38–49. | MR | Zbl
, , and , On the approximation of computing evolutionary trees. In: Proc. of the Eleventh Annual International Computing and Combinatorics Conference. Springer, Berlin, Heidelberg (2005) 115–123. | DOI | MR | Zbl
, , and , On the dominating set polytope. Eur. J. Combin. 29 (2008) 652–661. | DOI | MR | Zbl
and , One-node cutsets and the dominating set polytope. Discrete Math. 165/166 (1997) 101–123. | DOI | MR | Zbl
, and , Boolean-width of graphs. Theoret. Comput. Sci. 412 (2011) 5187–5204. | DOI | MR | Zbl
and , On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: FOCS ‘08. IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, 1975 (2008) 687–696. | DOI | MR | Zbl
, , , , and , 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–58. | Zbl
, and , Fundamentals of Domination in Graphs. CRC Press, Boca Raton, FL (1998). | MR
and , On variants of the spanning star forest problem. In: Proc. of FAW-AAIM (2011) 70–81. | Zbl
, , , and , Minimum-cost b -edge dominating sets on trees. In, Vol. 8880 of Lecture Notes Computer Sciences (2014) 195–207. | DOI | MR | Zbl
, Polytope des absorbants dans une classe de graphes seuil. Annal. Discrete Math. 17 (1983) 443–452. | MR | Zbl
, , , , and , Approximating the spanning star forest problem and its applications to genomic sequence alignment. In: Proc. of SODA (2007) 645–654. | MR | Zbl
, The maximum weight spanning star forest problem on cactus graphs. Discrete Math. Algorithms App. 7 (2015) 1550018. | DOI | MR | Zbl
, Some results on the dominating set polytope of a cycle. Technical Report CMU (2004).
and , Edge dominating sets in graphs. SIAM J. Appl Math. 38 (1980) 364–372. | DOI | MR | Zbl
Cité par Sources :
