×

On the star forest polytope for trees and cycles. (English) Zbl 1434.90162

Summary: 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 [V. H. Nguyen, Discrete Math. Algorithms Appl. 7, No. 2, Article ID 1550018, 10 p. (2015; Zbl 1316.05095)]. 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 M. Bouchakour et al. [Eur. J. Comb. 29, No. 3, 652–661 (2008; Zbl 1168.05340)], we give a complete linear description of \(SFP(G)\) when \(G\) is a cycle.

MSC:

90C27 Combinatorial optimization
90C10 Integer programming

References:

[1] A. Agra, D. Cardoso, O. Cerfeira and E. Rocha, A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (2005).
[2] S. Athanassopoulos, I. Caragiannis, C. Kaklamanis and M. Kyropoulou, An improved approximation bound for spanning star forest and color saving. In: MFCS. Springer, Berlin, Heidelberg (2009) 90-101. · Zbl 1250.68285
[3] M. Baïou and F. Barahona, On the integrality of some facility location polytopes. SIAM J. Discrete Math. 23 (2009) 665-679. · Zbl 1198.90332 · doi:10.1137/070706070
[4] M. Baïou, F. Barahona, Simple extended formulation for the dominating set polytope via facility location, Tech. Rep. RC25325, IBM Research (2012). · Zbl 1452.90308
[5] M. Baïou, F. Barahona, Algorithms for minimum weighted dominating sets in cycles and cacti, Tech. Rep. RC25488, IBM Research (2014). · Zbl 1452.90308
[6] M. Baïou and F. Barahona, The dominating set polytope via facility location. Combinatorial Optimization. ISCO 2014. In Vol. 8596 of Lecture Note Computer Sciences (2014) 38-49. · Zbl 1452.90308
[7] V. Berry, S. Guillemot, F. Nicholas and C. Paul, On the approximation of computing evolutionary trees. In: Proc. of the Eleventh Annual International Computing and Combinatorics Conference. Springer, Berlin, Heidelberg (2005) 115-123. · Zbl 1128.68554
[8] M. Bouchakour, T.M. Contenza, C.W. Lee and A.R. Mahjoub, On the dominating set polytope. Eur. J. Combin. 29 (2008) 652-661. · Zbl 1168.05340 · doi:10.1016/j.ejc.2007.03.010
[9] M. Bouchakour and A.R. Mahjoub, One-node cutsets and the dominating set polytope. Discrete Math. 165/166 (1997) 101-123. · Zbl 0872.90104
[10] B.-M. Bui-Xuan, J.A. Telle and M. Vatshelle, Boolean-width of graphs. Theoret. Comput. Sci. 412 (2011) 5187-5204. · Zbl 1225.68133 · doi:10.1016/j.tcs.2011.05.022
[11] D. Chakrabarty and G. Goel, 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. · Zbl 1263.90037
[12] N. Chen, R. Engelberg, C.T. Nguyen, P. Raghavendra, A. Rudra and G. Singh, 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 1171.05424
[13] T.W. Haynes, P.J. Slater and S.T. Hedetniemi, Fundamentals of Domination in Graphs. CRC Press, Boca Raton, FL (1998). · Zbl 0890.05002
[14] J. He and H. Liang, On variants of the spanning star forest problem. In: Proc. of FAW-AAIM (2011) 70-81. · Zbl 1329.68140
[15] T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, Minimum-cost b -edge dominating sets on trees. In, Vol. 8880 of Lecture Notes Computer Sciences (2014) 195-207. · Zbl 1432.68181 · doi:10.1007/978-3-319-13075-0_16
[16] A.R. Mahjoub, Polytope des absorbants dans une classe de graphes seuil. Annal. Discrete Math. 17 (1983) 443-452. · Zbl 0543.05050
[17] C.T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment. In: Proc. of SODA (2007) 645-654. · Zbl 1302.68324
[18] V.H. Nguyen, The maximum weight spanning star forest problem on cactus graphs. Discrete Math. Algorithms App. 7 (2015) 1550018. · Zbl 1316.05095 · doi:10.1142/S1793830915500184
[19] A. Saxena, Some results on the dominating set polytope of a cycle. Technical Report CMU (2004).
[20] M. Yannakakis and F. Gavril, Edge dominating sets in graphs. SIAM J. Appl Math. 38 (1980) 364-372. · Zbl 0455.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.