Abstract
We consider the k most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) 1-median (respectively 1-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the 1-median (respectively 1-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker 1-median (respectively 1-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the 1-median (respectively 1-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges 1-median and k most vital edges 1-center are NP-hard to approximate within a factor \(\frac{7}{5}-\epsilon\) and \(\frac{4}{3}-\epsilon\) respectively, for any ε> 0, while k most vital nodes 1-median and k most vital nodes 1-center are NP-hard to approximate within a factor \(\frac{3}{2}-\epsilon\), for any ε> 0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Arora, S., Lund, C.: Hardness of approximations. In: Approximation Algorithms for NP-hard Problems, pp. 399–446. PWS Publishing Company (1996)
Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, Department of Computer Science, University of Maryland (1995)
Bazgan, C., Toubaline, S., Tuza, Z.: Complexity of most vital nodes for independent set in graphs related to tree structures. In: Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010). Springer, Heidelberg (2010) (to appear in LNCS)
Brooks, R.L.: On colouring the nodes of a network. Mathematical Proceeing of the Cambridge Philosophical Society 37(2), 194–197 (1941)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162(1), 439–485 (2005)
Frederickson, G.N., Solis-Oba, R.: Increasing the weight of minimum spanning trees. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1996), pp. 539–546 (1996)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science 1(3), 237–267 (1976)
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Rudolf, G., Zhao, J.: On short paths interdiction problems: total and node-wise limited interdiction. Theory of Computing Systems 43(2), 204–233 (2008)
Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. In: Proceedings of the 35th Annual IEEE Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 819–830 (1994); Also published in SIAM Journal on Computing 28(1), 164-191 (1999)
Ries, B., Bentz, C., Picouleau, C., de Werra, D., Costa, M., Zenklusen, R.: Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid. Discrete Mathematics 310(1), 132–146 (2010)
Wood, R.K.: Deterministic network interdiction. Mathematical and Computer Modeling 17(2), 1–18 (1993)
Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M., Bentz, C.: Blockers and transversals. Discrete Mathematics 309(13), 4306–4314 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bazgan, C., Toubaline, S., Vanderpooten, D. (2010). Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems. In: Wu, W., Daescu, O. (eds) Combinatorial Optimization and Applications. COCOA 2010. Lecture Notes in Computer Science, vol 6508. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17458-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-17458-2_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17457-5
Online ISBN: 978-3-642-17458-2
eBook Packages: Computer ScienceComputer Science (R0)