Polyhedral study for the maximum bounded r-tree problem
Hervé L. M. Kerivin, Jinhua Zhao · 2014
Given an undirected graph G, a specific node r, and capacity on the nodes, the maximum bounded r-tree problem consists of finding a tree of G rooted at r containing as many nodes as possible with respect to the node capacities. This NP-hard optimization problem has been recently considered in the context of peer-to-peer networks. In this work, we study the associated polytope, in the space of edge variables. We introduce several families of facet-defining inequalities which lead to complete polyhedral descriptions of the polytope as well as total dual integrality of the defining linear system on trees and cycles. We also address their separation problems and present some preliminary computational results obtained by our branch-and-cut algorithm.