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

RAIRO - Operations Research (2010)

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

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

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