On the Star Forest Polytope for 4-Cactus Graphs
摘要
This paper investigates the polyhedral structure of the Maximum Weight Star Forest Problem (MWSFP) in an undirected weighted graph \(G = (V, E)\) , where each edge has a non-negative weight. A star in G is either an isolated node or a connected subgraph in which all edges share a common endpoint, and a star forest is a collection of disjoint stars. The objective of the MWSFP is to find a star forest with the maximum total edge weight. This problem is NP-hard in general but can be solved in polynomial time when G is a cactus graph [19]. In this paper, we provide a complete polyhedral description of the star forest polytope SFP(G) when G is a 4-cactus graph, a subclass of cactus graphs where each cycle has at most four edges. More precisely, we introduce a new class of facet-defining inequalities, called M-cactus inequalities, which hold for any graph. We then show that when G is a 4-cactus graph, the M-cactus inequalities, together with the non-negativity inequalities, completely describe SFP(G).