Labeled cuts in graphs

Lenwood Heath, Madhav Marathe

Abstract

In this paper, we study labeled extensions of the classical s,t-mincut problem, in which we are given a graph G=(V,E), two specific vertices s,t∈V, a set L of labels, and a labeling ℓ:E→L of the edges. The goal is to choose a subset L′⊆L of labels, so that s and t become disconnected when deleting the edges with labels in L′. We give an algorithm with an O(n2/3) approximation factor guarantee, which improves the View the MathML source approximation guarantee of Zhang et al. (2009) [16]. We also consider variants in which selected subsets of paths between s and t have to be removed (instead of all paths). These labeled cut problems are much harder than the classical mincut problem.