TR-2017-07

Blocking optimal structures

Kristóf Bérczi, Attila Bernáth, Tamás Király, Gyula Pap



Abstract

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:

@techreport{egres-17-07,
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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-07}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!