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

Elisabeth Gassner

RAIRO - Operations Research (2010)

  • Volume: 44, Issue: 3, page 241-249
  • ISSN: 0399-0559

Abstract

top
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 L1-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.

How to cite

top

Gassner, Elisabeth. "The partial inverse minimum cut problem with L1-norm is strongly NP-hard." RAIRO - Operations Research 44.3 (2010): 241-249. <http://eudml.org/doc/250836>.

@article{Gassner2010,
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 L1-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. },
author = {Gassner, Elisabeth},
journal = {RAIRO - Operations Research},
keywords = {Partial inverse minimum cut problem; partial inverse minimum cut problem},
language = {eng},
month = {10},
number = {3},
pages = {241-249},
publisher = {EDP Sciences},
title = {The partial inverse minimum cut problem with L1-norm is strongly NP-hard},
url = {http://eudml.org/doc/250836},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Gassner, Elisabeth
TI - The partial inverse minimum cut problem with L1-norm is strongly NP-hard
JO - RAIRO - Operations Research
DA - 2010/10//
PB - EDP Sciences
VL - 44
IS - 3
SP - 241
EP - 249
AB - 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 L1-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.
LA - eng
KW - Partial inverse minimum cut problem; partial inverse minimum cut problem
UR - http://eudml.org/doc/250836
ER -

References

top
  1. R.K. Ahuja and J.B. Orlin, Inverse optimization. Oper. Res.49 (2001) 771–783.  Zbl1163.90764
  2. L.R. Ford, Jr. and D.R. Fulkerson, Maximal flow through a network. Canad. J. Math.8 (1956) 399–404.  Zbl0073.40203
  3. M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci.1 (1976) 237–267.  Zbl0338.05120
  4. C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods, and results. J. Comb. Optim.8 (2004) 329–361.  Zbl1084.90035
  5. T.C. Lai and J.B. Orlin, The complexity of preprocessing. Research Report of Sloan School of Management, MIT (2003).  
  6. J.B. Orlin, Partial inverse optimization problems. Working paper, Sloan School of Management, MIT.  
  7. X. Yang, Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO-Oper. Res.35 (2001) 117–126.  Zbl0993.90068
  8. J. Zhang and M.-C. Cai, Inverse problem of minimum cuts. Math. Methods Oper. Res.47 (1998) 51–58.  Zbl0941.90013

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.