  Given a graph G=(V,E) with a label set L = {l_1, l_2, ..., l_q}, in which
each edge has a label from L, a source s in V, and a sink t in V, the Min Label
s-t Cut problem asks to pick a set L' subseteq L of labels with minimized
cardinality, such that the removal of all edges with labels in L' from G
disconnects s and t. This problem comes from many applications in real world,
for example, information security and computer networks. In this paper, we
study two linear programs for Min Label s-t Cut, proving that both of them have
large integrality gaps, namely, Omega(m) and Omega(m^{1/3-epsilon}) for the
respective linear programs, where m is the number of edges in the graph and
epsilon > 0 is any arbitrarily small constant. As Min Label s-t Cut is NP-hard
and the linear programming technique is a main approach to design approximation
algorithms, our results give negative answer to the hope that designs better
approximation algorithms for Min Label s-t Cut that purely rely on linear
programming.
