TR-2015-09

Blocking optimal k-arborescences

Attila Bernáth, Tamás Király



Abstract

Given a digraph $D=(V,A)$ and a positive integer $k$, an arc set $F\subseteq A$ is called a $k$-arborescence if it is the disjoint union of $k$ spanning arborescences. The problem of finding a minimum cost $k$-arborescence is known to be polynomial-time solvable using matroid intersection. In this paper we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost $k$-arborescence. For $k=1$, the problem was solved in [A. Bernáth, G. Pap , Blocking optimal arborescences, IPCO 2013]. In this paper we give an algorithm for general $k$ that has polynomial running time if $k$ is fixed.


Bibtex entry:

@techreport{egres-15-09,
AUTHOR = {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s},
TITLE = {Blocking optimal k-arborescences},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-09}
}


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