Abstract
Motivated by applications in risk management of computational systems, we focus our attention on a special case of the partial vertex cover problem, where the underlying graph is assumed to be a tree. Here, we consider four possible versions of this setting, depending on whether vertices and edges are weighted or not. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, has not been determined yet. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain intractable in trees, and which can be efficiently solved. In particular, we propose a pseudo-polynomial DP-based algorithm for the most general case of having weights on both edges and vertices, which is proven to be NP-hard. This algorithm provides a polynomial-time solution method when weights are limited to edges, and combined with additional scaling ideas, leads to an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well.
V. Mkrtchyan—This research has been supported in part by the Air Force of Scientific Research through Award FA9550-12-1-0199.
K. Subramani—Supported by the National Science Foundation through Award CCF-1305054 and also supported by the Air Force of Scientific Research through Award FA9550-12-1-0199.
Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energys National Nuclear Security Administration under contract DE-AC04-94AL85000.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
That is, having an exponent of poly-logarithmic order (in the input size).
- 2.
In addition to vertex costs and edge profits, which are common to all states.
References
Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137–144 (2001)
Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D.: Approximation of partial capacitated vertex cover. SIAM J. Discrete Math. 24(4), 1441–1469 (2010)
Bshouty, N.H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 298–308 (1998)
Caskurlu, B., Gehani, A., Bilgin, C.Ç., Subramani, K.: Analytical models for risk-based intrusion response. Comput. Netw. 57(10), 2181–2192 (2013)
Caskurlu, B., Subramani, K.: On partial vertex cover on bipartite graphs and trees (2013). arXiv: 1304.5934
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005)
Frederickson, G.N., Johnson, D.B.: Finding \(k\)-th paths and \(p\)-centers by generating and searching good data structures. J. Algorithms 4(1), 61–80 (1983)
Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)
Gehani, A.: Performance-sensitive real-time risk management is NP-hard. In: Workshop on Foundations of Computer Security, Affiliated with the 19th IEEE Symposium on Logic in Computer Science (2004)
Halperin, E., Srinivasan, A.: Improved approximation algorithms for the partial vertex cover problem. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 161–174. Springer, Heidelberg (2002). doi:10.1007/3-540-45753-4_15
Hochbaum, D.S.: The t-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 111–122 (1998)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, USA (1972)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within \(2-\epsilon \). J. Comput. Syst. Sci. 74(3), 335–349 (2008)
Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica 55(1), 227–239 (2009)
Moser, H.: Exact algorithms for generalizations of vertex cover. Master thesis, Jena University (2005)
N.B. of standards. In: 4th Computer Security Risk Management Model Builders Workshop, University of Maryland, College Park, Maryland, August 1991
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 588–597 (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Mkrtchyan, V., Parekh, O., Segev, D., Subramani, K. (2017). The Approximability of Partial Vertex Covers in Trees. In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science(), vol 10139. Springer, Cham. https://doi.org/10.1007/978-3-319-51963-0_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-51963-0_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-51962-3
Online ISBN: 978-3-319-51963-0
eBook Packages: Computer ScienceComputer Science (R0)