On the minimum s-t cut problem with budget constraints

We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = ( V , A ) with two distinguished nodes s and t , k non-negative cost functions c 1 , … , c k : A → Z + , and k - 1 budget bounds b 1 , … , b k - 1 . The goal is to find a s - t cut C sati...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2024, Vol.203 (1-2), p.421-442
Main Authors: Aissi, Hassene, Mahjoub, A. Ridha
Format: Article
Language:English
Subjects:
Budgets
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Cost function
Full Length Paper
Graph theory
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Theoretical
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = ( V , A ) with two distinguished nodes s and t , k non-negative cost functions c 1 , … , c k : A → Z + , and k - 1 budget bounds b 1 , … , b k - 1 . The goal is to find a s - t cut C satisfying the budget constraints c h ( C ) ⩽ b h , for h = 1 , … , k - 1 , and whose cost c k ( C ) is minimum. In this paper we discuss the linear relaxation of the problem and introduce a strict partial ordering on its solutions. We give a necessary and sufficient condition for which it has an integral optimal minimal (with respect to this ordering) basic solution. We also show that recognizing whether this is the case is NP-hard.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-023-01987-9