Minimum Label s-t Cut has Large Integrality Gaps

Peng Zhang, Linqing Tang

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 pi…