2015/06/18 by Attila Bernáth, Bernáth, Attila, Gyula Pap +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1506.05677
arxiv created 2015/06/18 · arxiv updated 2015/06/19
The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph D=(V,A) with a designated root node r∈ V and arc-costs c:A→ ℝ, find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give solves a weighted version as well, in which a nonnegative weight function w:A→ ℝ+ (unrelated to c) is also given, and we want to find a subset H of the arc set such that H intersects every minimum c-cost r-arborescence, and w(H)=∑a∈ Hw(a) is minimum. The running time of the algorithm is O(n3T(n,m)), where n and m denote the number of nodes and arcs of the input digraph, and T(n,m) is the time needed for a minimum s-t cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.