The label cut problem with respect to path length and label frequency

Given a graph with labels defined on edges and a source-sink pair ( s , t ) , the Label s - t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l max , the maximum length of any s - t path (only applies to Label s - t Cut), and f max , the maximum number of appearances of any label in the graph (applies to the two problems). We show that l max = 2 and f max = 2 are two complexity thresholds for Label s - t Cut. Furthermore, we give (i) an O * ( c k ) time parameterized algorithm for Label s - t Cut with l max bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l max - 1 < c < l max , (ii) a combinatorial l max -approximation algorithm for Label s - t Cut, and (iii) a polynomial time exact algorithm for Global Label Cut with f max bounded from above. We give an FPT algorithm for Label s - t Cut in a special case.We give a pure combinatorial approximation algorithm for Label s - t Cut.We give a polynomial time exact algorithm for Global Label Cut in a special case.