The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams (Nash-Williams, 1961) and Tutte (Tutte, 1961) on packing spanning trees by adapting Lovász’ proof (Lovász, 1976) of the seminal result of Edmonds (Edmonds, 1973) on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa (Katoh and Tanigawa, 2013) on matroid-based packing of rooted trees by characterizing the existence of such a packing satisfying the following further conditions: for every vertex v , there are given a lower bound f ( v ) and an upper bound g ( v ) on the number of trees rooted at v and there are given a lower bound α and an upper bound β on the total number of roots. We also answer the hypergraphic version of the problem. Furthermore, we are able to solve the augmentation version of the latter problem, where the goal is to add a minimum number of edges to have such a packing. The methods developed in this paper to solve these problems may have other applications in the future.

A well known technique to reduce the search space in integer programming is known as variable fixing or reduced cost strengthening . The reduced costs given by an optimal dual solution of the linear relaxation can be used to strengthen the bounds of the variables but this filtering is incomplete. We show how reduced costs can be used to achieve Arc-Consistency (AC), i.e. a complete filtering, of a global constraint with a cost variable and an assignment cost for each value. We assume that an ideal Integer Linear Programming (ILP) formulation is available i.e. the convex hull of the characteristic vectors of the supports is known. A detailed analysis of reduced cost based filtering is proposed. We characterize arc-consistency based on complementary slackness i.e. completeness of reasoning as opposed to only optimality. We also give a simple sufficient condition allowing a set of dual solutions to ensure arc-consistency through reduced costs. In practice, when the constraint has a such an ideal ILP, n dual solutions are always enough to achieve AC (where n is the number of variables of the global constraint). It extends the work presented in [26] for satisfaction problems and in [17] for the specific case of the minimum weighted alldifferent constraint. Our analysis is illustrated on constraints related to the assignment and shortest path problem and also demonstrated on the weighted stable set problem in chordal graphs. A novel AC algorithm is proposed in this latter case based on reduced costs.