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,..., c~k : A →Z_+, and k - 1 budget bounds b_1,...,b_(k-1) where k is a constant. The goal is to find a s - t cut C satisfying budget constraints c~h(C)≤ b_h, for h = 1,... ,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.