Abstract
Given an edge weighted graph, and an acyclic edge set, the goal of partial inverse maximum spanning tree problem is to modify the weight function as little as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the weighted Hamming distance. Under the weighted sum Hamming distance, if the given edge set has at least two edges, we show that this problem is APX-Hard even without the capacitated constraint; if the given edge set contains only one edge, we present a strongly polynomial time algorithm to solve it. Under the weighted bottleneck Hamming distance, we present an algorithm with time complexity \(O(m\log ^2 m)\), where m is the number of edges of the given graph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja RK, Orlin JB (2000) A faster algorithm for the inverse spanning tree problem. J Algorithms 34:177–193
Bondy JA, Murty USR (2008) Graph theory. Springer, New York
Cai M-C, Duin CW, Yang X, Zhang J (2008) The partial inverse minimum spanning tree problem when weight increasing is forbidden. Eur J Oper Res 188:348–353
Cheriyan J, Hagerup T, Mehlhorn K (1996) An \(O(n^3)\)-time maximum-flow algorithm. SIAM J Comput 25(6):1144–1170
Dahlhaus E, Johnson DS, Papadimitriou CH, Seymour PD, Yannakakis M (1994) The complexity of multiterminal cuts. SIAM J Comput 23(4):864–894
Dell’Amico M, Maffioli F, Malucelli F (2003) The Base-matroid and inverse combinatorial optimization problems. Discret Appl Math 128:337–353
Gassner E (2010) The partial inverse minimum cut problem with \(L_1\)-norm is strongly NP-hard. RAIRO Oper Res 44:241–249
Guan X, Zhang B (2012) Inverse 1-median problem on trees under weighted Hamming distance. J Glob Optim 54:75–82
Guan X, Pardalos PM, Zuo X (2015) Inverse Max+Sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) Norm. J Glob Optim 61:165–182
He Y, Zhang B, Yao E (2005) Weighted inverse minimum spanning tree problems under hamming distance. J Comb Optim 9:91–100
Hochbaum DS (2003) Efficient algorithms for the inverse spanning-tree problem. Oper Res 51(5):785–797
Hochbaum DS, Queyranne M (2003) Minimizing a convex cost closure set. SIAM J Discret Math 16(2):192–207
Lai T, Orlin J (2003) The complexity of preprocessing. In: Research report of Sloan school of management, MIT
Li S, Zhang Z, Lai H-J (2016) Algorithm for constraint partial inverse matroid problem with weight increase forbidden. Theor Comput Sci 640:119–124
Li X, Zhang Z, Du D-Z (2018) Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm. J Glob Optim 70:677–685
Liu L, Wang Q (2009) Constrained inverse min-max spanning tree problems under the weighted Hamming distance. J Glob Optim 43:83–95
Liu L, Yao E (2007) A weighted inverse minimum cut problem under the bottleneck type Hamming distance. Asia-Pac J Oper Res 24(5):725–736
Liu L, Yao E (2008) Inverse min-max spanning tree problem under the weighted sum-type Hamming distance. Theor Comput Sci 396:28–34
Liu L, Yao E (2013) Weighted inverse maximum perfect matching problems under the Hamming distance. J Glob Optim 55:549–557
Liu L, Zhang J (2006) Inverse maximum flow problems under the weighted Hamming distance. J Comb Optim 12(4):395–408
Liu L, Chen Y, Wu B, Yao E (2012) Weighted inverse minimum cut problem under the sum-type Hamming distance. Lect Notes Comput Sci 7285:26–35
Nguyen KT, Chassein A (2015) The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. Eur J Oper Res 247:774–781
Nguyen KT, Sapasian AR (2016) The inverse 1-center problem on trees with varible edge lengths under Chebyshev norm and Hamming distance. J Comb Optim 32(3):872–884
Orlin JB (2013) Maxflows in \(O(nm)\) time, or better. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing (STOC 2013), pp 765–774
Papadimitriou C, Yannakakis M (1988) Optimization, approximations, and complexity classes. In: Proceedings of the twentieth annual ACM symposium on theory of computing (STOC 1988), pp 229–234
Sokkalingam PT, Ahuja RK, Orlin JB (1999) Solving inverse spanning tree problems through network flow techniques. Oper Res 47(2):291–298
Wang L (2011) Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem. J Glob Optim 51(3):463–471
Yang X (2001) Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO Oper Res 35:117–126
Yang X, Zhang J (2007a) Partial inverse assignment problem under \(l_1\) norm. Oper Res Lett 35:23–28
Yang X, Zhang J (2007b) Inverse sorting problem by minimizing the total weighted number of changers and partial inverse sorting problems. Comput Optim Appl 36(1):55–66
Zhang J, Xu S, Ma Z (1997) An algorithm for inverse minimum spanning tree problem. Optim Methods Softw 8(1):69–84
Zhang B, Zhang J, He Y (2005) The center location improvement problem under the Hamming distance. J Comb Optim 9(2):187–198
Zhang B, Zhang J, He Y (2006a) Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J Glob Optim 34:467–474
Zhang B, Zhang J, Qi L (2006b) The shortest path improvement problems under Hamming distance. J Comb Optim 12(4):351–361
Zhang Z, Li S, Lai H-J, Du D-Z (2016) Algorithms for the partial inverse matroid problem in which weights can only be increased. J Glob Optim 65(4):801–811
Acknowledgements
This research is partially supported by National Key Research and Development Plan of China (No. 2017YFB0202101), NSFC (Nos. 11571155 and 11871256) and the Fundamental Research Funds for the Central Universities (No. lzujbky-2017-163).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, X., Shu, X., Huang, H. et al. Capacitated partial inverse maximum spanning tree under the weighted Hamming distance. J Comb Optim 38, 1005–1018 (2019). https://doi.org/10.1007/s10878-019-00433-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00433-x