On the Boolean Quadric Forest Polytope

We study the Boolean Quadric Forest Polytope, namely the convex hull of the “extended” edge incidence-vectors of forests of a complete graph – extended by the unusual linearization of the quadratic terms. Our motivation is to provide a mathematical foundation for attacking the minimum quadratic-cost forest problem via branch-and-cut methods of integer programming. We determine several families of facets of the Boolean Quadric Forest Polytope and relate them to the Boolean Quadric Polytope as well as the Forest Polytope. We give polynomial-time separation procedures for some of the families of facets.