Blocking optimal arborescences (Q507342)

A spanning arborescence of a directed graph \(D\) with vertex set \(V\) and arc set \(A\) is a spanning tree (in the undirected version of \(D\)) and each vertex has in-degree not more than one. Thus there is exactly one vertex with in-degree zero which is called root vertex. The minimum cost arborescence problem for a given digraph \(D\) and a root vertex \(r\) and cost function \(c\), that assigns each arc a real cost value, is to find an arborescence \(B\) (as a subset of \(A\)) rooted at \(r\) such that the total cost of all arcs in \(B\) is minimal. The problem is equivalent to the one where \(r\) is not fixed. The question arises how to find a subset \(H\) of the arc set such that \(H\) intersects every minimum cost arborescence and \(H\) contains a minimum number of arcs. The problem is a measure of robustness as it asks for the minimum number of arcs that need to be deleted in order to destroy all minimum cost arborescences. The authors give an efficient polynomial time algorithm for the more general problem where the arc set \(H\) intersects each minimum cost arborescence and the total weight of \(H\) is minimum.