Approximating Minimum Label s-t Cut via Linear Programming

摘要

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 ∈ V together with a sink t ∈ 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/OPT)~(1/2)),O(n~(2/3)/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 Ω((m/OPT)~(1/2-∈)).