We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the star forest polytope for trees and cycles.
- Authors
Aider, Meziane; Aoudia, Lamia; Baïou, Mourad; Mahjoub, A. Ridha; Nguyen, Viet Hung
- Abstract
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.
- Subjects
STELLAR structure; DOMINATING set; POLYNOMIAL time algorithms; NP-hard problems; UNDIRECTED graphs; POLYTOPES
- Publication
RAIRO -- Operations Research, 2019, Vol 53, Issue 5, p1763
- ISSN
0399-0559
- Publication type
Article
- DOI
10.1051/ro/2018076