The Generalized Minimum Branch Vertices Problem: Properties and Polyhedral Analysis

This article introduces the Generalized Minimum Branch Vertices problem. Given an undirected graph, where the set of vertices is partitioned into clusters, the Generalized Minimum Branch Vertices problem consists of finding a tree spanning exactly one vertex for each cluster and having the minimum number of branch vertices, namely vertices with degree greater than two. When each cluster is a singleton, the problem reduces to the well-known Minimum Branch Vertices problem, which is NP-hard. We show some properties that any feasible solution to the problem has to satisfy. Some of these properties can be used to determine useless vertices or edges, which can be removed to reduce the size of the instances. We propose an integer linear programming formulation for the problem, we derive the dimension of the polytope, we study the trivial inequalities and introduce two new classes of valid inequalities, that are proved to be facet-defining.