Approximation and hardness results for label cut and related problems

We investigate a natural combinatorial optimization problem called the Label Cut problem. Given an input graph G with a source s and a sink t, the edges of G are classified into different categorie...