Blocking optimal structures

In particular, we study the following five kinds of families: minimum cost k-spanning trees (unions of k edge-disjoint spanning trees), minimum cost s-rooted k-arborescences (unions of k arc-disjoint arborescences rooted at node s), minimum cost (directed or undirected) k-braids between nodes s and t (unions of k edge-disjoint s-t paths), and minimum cost (directed or undirected) k-edge-connected subgraphs. We focus on the special cases when either c or w is uniform. For the case c≡0 (i.e. we want to block all combinatorial objects, not just the optimal ones), we show that most of the problems are NP-complete. In the other case, when w≡1 (a minimum cardinality transversal problem for F), most of our problems turn out to be polynomial-time solvable.