Inverse maximum flow and minimum cut problems

Abstract

In this paper we consider two inverse problems in combinatorial optimization: inverse maximum flow (IMF) problem and inverse minimum cut (IMC) problem. IMF (or IMC) problem can be described as: how to change the capacity vector C of a network as little as possible so that a given flow (or cut) becomes a maximum flow (or minimum cut) in the network. After discussing some characteristics of these problems, we propose strongly polynormial algorithms for the two inverse problems.

Keywords:

• Inverse Problems
• network Programming
• Maximum Flow
• Minimum Cut
• Maximum Weight Flow

^†This work is supported by Chroucher Foundation (Grant 9050030) and Hong Kong Research Grant Council (CERG-CITYU-9040189)

‡Corresponding author

^†This work is supported by Chroucher Foundation (Grant 9050030) and Hong Kong Research Grant Council (CERG-CITYU-9040189)

‡Corresponding author

Notes

^†This work is supported by Chroucher Foundation (Grant 9050030) and Hong Kong Research Grant Council (CERG-CITYU-9040189)

‡Corresponding author