Blocking unions of arborescences

作     者：Bernath, Attila Pap, Gyula 

作者机构：Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Pazmany Peter Setany 1-C H-1117 Budapest Hungary 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2016年第22卷第PartB期

页      面：277-290页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：ERC StG Hungarian Scientific Research Fund (OTKA) [NK105645, K109240] OTKA [K109240] European Research Council (ERC) Funding Source: European Research Council (ERC) 

主　　题：Arborescences Polynomial algorithm Minimum transversal 

摘      要：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.