Given a digraph D = (V, A) and a positive integer k, a subset B subset of A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A -> R are given, minimizing the cost of a k-arborescence is well-known to be tractable. In this paper we take on the following problem: what is the minimum cardinality of a set of arcs the removal of which destroys every minimum c-cost karborescence. Actually, the more general weighted problem is also considered, that is, arc weights w : A -> R+ (unrelated to c) are also given, and the goal is to find a minimum weight set of arcs the removal of which destroys every minimum c-cost k-arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper (Bernath and Pap, 2013) we solved this problem for k = 1. This work reports on other partial results on the problem. We solve the case when both c and w are uniform-that is, find a minimum size set of arcs that covers all k-arborescences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Barasz et al. (2005) saying that the family of so-called in-solid sets (sets with the property that every proper subset has a larger in-degree) satisfies the Helly-property, and thus can be (efficiently) represented as a subtree hypergraph. We also give an algorithm for the case when only c is uniform but w is not. This algorithm is only polynomial if k is not part of the input. (C) 2016 Published by Elsevier B.V.
展开▼
