Simpler and Better Approximation Algorithms for the Unweighted Minimum Label s-t Cut Problem

摘要

Given a graph with a label set , in which each edge has a label from L, and a source together with a sink , the Minimum Label s-t Cut problem asks to pick a set of labels with minimized cardinality, such that the removal of all edges with labels in from G disconnects s and t. Let and . The previous best known approximation ratio for this problem in literature is . We present two simple and purely combinatorial approximation algorithms for the problem with ratios and , where is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., ). The latter result improves the previous ratio , as we can always assume that is a super-constant.