  Minimum Label Cut (or Hedge Connectivity) problem is defined as follows:
given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which,
each edge is labeled (with one or multiple labels) from a label set
$L=\{\ell_1,\ell_2, ..., \ell_{|L|}\}$, the edges may be weighted with weight
set $W =\{w_1, w_2, ..., w_m\}$, the label cut problem(hedge connectivity)
problem asks for the minimum number of edge sets(each edge set (or hedge) is
the edges with the same label) whose removal disconnects the source-sink pair
of vertices or the whole graph with minimum total weights(minimum cardinality
for unweighted version). This problem is more general than edge connectivity
and hypergraph edge connectivity problem and has a lot of applications in MPLS,
IP networks, synchronous optical networks, image segmentation, and other areas.
However, due to limited communications between different communities, this
problem was studied in different names, with some important existing literature
citations missing, or sometimes the results are misleading with some errors. In
this paper, we make a further investigation of this problem, give uniform
definitions, fix existing errors, provide new insights and show some new
results. Specifically, we show the relationship between non-overlapping
version(each edge only has one label) and overlapping version(each edge has
multiple labels), by fixing the error in the existing literature; hardness and
approximation performance between weighted version and unweighted version and
some useful properties for further research.
