RAIRO - Operations Research

Table of Contents - July 2010 - Volume 44, Issue 03  

Research Article

The partial inverse minimum cut problem with L 1-norm is strongly NP-hard

Gassner, Elisabeth

Department of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria. gassner@opt.math.tu-graz.ac.at

Abstract

The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L 1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res. 35 (2001) 117–126] for this problem with additional bound constraints is not correct.

(Received September 22 2009)

(Accepted August 7 2010)

(Online publication October 25 2010)

Key Words:

  • Partial inverse minimum cut problem

Mathematics Subject Classification:

  • 90C27;
  • 90C60;
  • 68Q25