The Minimum Weight In-Tree Cover Problem

Given a directed graph D = (V,A) with a root s ∈ V such that a non-negative rational weight is associated with each arc in A, we consider the problem for finding a set of minimum weight k spanning in-trees rooted at s which cover A. Here the weight of k spanning in-trees is defined as the sum of weights of all arcs contained in these in-trees. We will show that this problem can be solved in polynomial time. For this, we first consider the set of linear inequalities in ℝ^A that coincides with the convex hull P_ic(D) of a {pipe}A{pipe}-dimensional positive integral vector x such that we can cover A by k spanning in-trees rooted at s such that e ∈ A is contained in x_e in-trees where ℝ represents the set of reals. After this, we will show that the separation problem for this polytope can be solved in polynomial time, which implies the polynomial time solvability of the minimum weight in-tree cover problem in conjunction with the ellipsoid method. Furthermore, we will consider the generalization of the minimum in-tree cover problem such that the input directed graph has multiple roots. Although this problem is still open, we give the generalization of the result presented by Vidyasankar [13] which is used to derive the set of linear inequalities which determine P_ic(D) to the case of multiple roots.