|
Published in:
We consider weighted blocking problems
(a.k.a. weighted transversal problems) of the following form. Given a
finite set $S$, weights $w:S\to \Rset_+$, and a family $\cF\subseteq
2^S$, find $\min \{w(H): H\subseteq S,\ H $ intersects every member of
$\cF\}$. In our problems $S$ is the set of edges of a (directed or undirected)
graph and $\cF$ is the family of optimal solutions of a combinatorial
optimization problem with respect to a cost function $c:S \to \Rset_+$.
Note that the cost function $c$ that defines the family and the weight
function $w$ in the weighted transversal problem are not related.
In particular, we study the following four 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$), and minimum cost (directed or undirected) $k$-braids
between nodes $s$ and $t$ (unions of $k$ edge-disjoint $s$-$t$ paths).
We focus on the special cases when either $c$ or $w$ is uniform.
For the case $c\equiv 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\equiv 1$ (a minimum
cardinality transversal problem for $\cF$), most of our problems
turn out to be polynomial-time solvable.
We also consider the problem of blocking
$k$-edge-connectivity, which is related to both
blocking \ksptree s and blocking $k$-braids.
We show that the undirected case can be solved in polynomial time using the ideas of
Zenklusen's connectivity interdiction algorithm. In contrast,
the directed version is shown to be NP-complete.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s and Pap, Gyula}, |
| TITLE | = | {Blocking optimal structures}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2017}, |
| NUMBER | = | {TR-2017-07} |