Minimum-weight subgraphs with unicyclic components and a lower-bounded girth

This article focuses on the problem of computing a minimum-weight subgraph with unicyclic connected components. Although this problem is generally easy, it becomes difficult when a girth constraint is added. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Hence, the problem is solved by a cutting-plane algorithm based on these inequalities and using a compact formulation derived from the transversality of the bicircular matroid. Numerical results are also presented.