On the Linear Relaxation of the \(s-t\)-cut Problem with Budget Constraints

We consider in this paper a generalization of the minimum \(s-t\) cut problem. Suppose we are given a directed graph \(G=(V,A)\) with two distinguished nodes s and t, k non-negative arcs cost functions \(c^1,\ldots ,c^k:A \rightarrow \mathbb {Z}_+\), and \(k-1\) budget bounds \(b_1, \ldots ,b_{k-1}\) where k is a constant. The goal is to find a \(s-t\) cut C satisfying budget constraints \(c^h(C) \leqslant b_h\), for \(h = 1,\ldots ,k-1\), and whose cost \(c^k(C)\) is minimum. We study the linear relaxation of the problem and give necessary and sufficient conditions for which it has an integral optimal basic solution.