O problema da k-floresta com máximo número de folhas

Abstract

Given a simple connected graph and a positive integer k, the maximum leaf k-forest problem consists in finding a spanning forest with as many leaves as possible and no more than k components. We propose the first mathematical models for the problem as well as valid inequalities. For k = 1, we have the known maximum leaf spanning tree problem (MLSTP). In particular, for this problem, the new inequalities have proved to be very efficient. Two of the models we propose in this work generalize formulations found in the literature for the MLSTP and are based on formulations that describe the polytope of spanning trees and arborescences. We also present new characterizations for the problem, which makes easy to express it in an alternative way, where we look for a set of leaves that generate an optimal solution and, once we have such set, we can obtain a solution to the problem in polynomial time. As a consequence, we propose a model called (MB) which we solve by using an iterative method based on Benders decomposition for k = 1 and, for the general case, a formulation called (MVE) and a model (MFA) exploring network flow. We perform computational experiments and analyze the performance of our models. In particular, for k = 1, we compare our results with the ones obtained by existing formulations for MLSTP. We emphasize model (MFA) for its simplicity to implement and for not demanding sophisticated cutting or separation techniques. In addition, for k = 1, this model was the unique to find optimal solutions for the whole set of instances, outperforming MLSTP models from the literature. It is also worth noting that, for k = 1, model (MB) was considerably more efficient than the other ones when considering instances with higher edge densities.