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.
Mots-clés : partial inverse minimum cut problem
@article{RO_2010__44_3_241_0, author = {Gassner, Elisabeth}, title = {The partial inverse minimum cut problem with {L1-norm} is strongly {NP-hard}}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {241--249}, publisher = {EDP-Sciences}, volume = {44}, number = {3}, year = {2010}, doi = {10.1051/ro/2010017}, mrnumber = {2762795}, zbl = {1206.90141}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2010017/} }
TY - JOUR AU - Gassner, Elisabeth TI - The partial inverse minimum cut problem with L1-norm is strongly NP-hard JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2010 SP - 241 EP - 249 VL - 44 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2010017/ DO - 10.1051/ro/2010017 LA - en ID - RO_2010__44_3_241_0 ER -
%0 Journal Article %A Gassner, Elisabeth %T The partial inverse minimum cut problem with L1-norm is strongly NP-hard %J RAIRO - Operations Research - Recherche Opérationnelle %D 2010 %P 241-249 %V 44 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2010017/ %R 10.1051/ro/2010017 %G en %F RO_2010__44_3_241_0
Gassner, Elisabeth. The partial inverse minimum cut problem with L1-norm is strongly NP-hard. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 3, pp. 241-249. doi : 10.1051/ro/2010017. http://www.numdam.org/articles/10.1051/ro/2010017/
[1] Inverse optimization. Oper. Res. 49 (2001) 771-783. | Zbl
and ,[2] Maximal flow through a network. Canad. J. Math. 8 (1956) 399-404. | Zbl
and ,[3] Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237-267. | Zbl
, and ,[4] Inverse combinatorial optimization: a survey on problems, methods, and results. J. Comb. Optim. 8 (2004) 329-361. | Zbl
,[5] The complexity of preprocessing. Research Report of Sloan School of Management, MIT (2003).
and ,[6] Partial inverse optimization problems. Working paper, Sloan School of Management, MIT.
,[7] Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO-Oper. Res. 35 (2001) 117-126. | Numdam | Zbl
,[8] Inverse problem of minimum cuts. Math. Methods Oper. Res. 47 (1998) 51-58. | Zbl
and ,Cité par Sources :