  In the weighted (minimum) {\sf Label $s$-$t$ Cut} problem, we are given a
(directed or undirected) graph $G=(V,E)$, a label set $L = \{\ell_1, \ell_2,
\dots, \ell_q \}$ with positive label weights $\{w_\ell\}$, a source $s \in V$
and a sink $t \in V$. Each edge edge $e$ of $G$ has a label $\ell(e)$ from $L$.
Different edges may have the same label. The problem asks to find a minimum
weight label subset $L'$ such that the removal of all edges with labels in $L'$
disconnects $s$ and $t$.
  The unweighted {\sf Label $s$-$t$ Cut} problem (i.e., every label has a unit
weight) can be approximated within $O(n^{2/3})$, where $n$ is the number of
vertices of graph $G$. However, it is unknown for a long time how to
approximate the weighted {\sf Label $s$-$t$ Cut} problem within $o(n)$. In this
paper, we provide an approximation algorithm for the weighted {\sf Label
$s$-$t$ Cut} problem with ratio $O(n^{2/3})$. The key point of the algorithm is
a mechanism to interpret label weight on an edge as both its length and
capacity.
