06051335

a

06051335 Tang, Linqing Zhang, Peng Approximating minimum label $s$-$t$ cut via linear programming. Fern\'andez-Baca, David (ed.), LATIN 2012: Theoretical informatics. 10th Latin American symposium, Arequipa, Peru, April 16--20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29343-6/pbk). Lecture Notes in Computer Science 7256, 655-666 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-29344-3_55

Summary: We consider the Minimum Label $s$-$t$ Cut problem. Given an undirected graph $G = (V,E)$ with a label set $L$, in which each edge has a label from $L$, and a source $s \in V$ together with a sink $t \in V$, the goal of the Minimum Label $s$-$t$ Cut problem is to pick a subset of labels of minimized cardinality, such that the removal of all edges with these labels from $G$ disconnects $s$ and $t$. We present a $min \{ O((m/\text{OPT})^{1/2}), O(n ^{2/3}/\text{OPT} ^{1/3}) \}$-approximation algorithm for the Minimum Label $s$-$t$ Cut problem using linear programming technique, where $n = |V|, m = |E|$, and OPT is the optimal value of the input instance. This result improves the previously best known approximation ratio $O(m ^{1/2})$ for this problem (Zhang et al., JOCO 21(2), 192-208 (2011)), and gives the first approximation ratio for this problem in terms of $n$. Moreover, we show that our linear program relaxation for the Minimum Label $s$-$t$ Cut problem, even in a stronger form, has integrality gap $\Omega ((m/\text{OPT})^{1/2 - \epsilon })$.