The partial inverse minimum cut problem with L1‐norm is strongly NP‐hard

The partial inverse minimum cut problem with L1‐norm is strongly NP‐hard

0.00 Avg rating0 Votes
Article ID: iaor20112578
Volume: 44
Issue: 3
Start Page Number: 241
End Page Number: 249
Publication Date: Jul 2010
Journal: RAIRO - Operations Research
Authors:
Keywords: minimum cuts
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.

Reviews

Required fields are marked *. Your email address will not be published.