On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs

Abstract : Graphs are often used to model risk management in various systems. Particularly, Caskurlu et al. in [6] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. It is well-known that the vertex cover problem is in P on bipartite graphs; however, the computational complexity of the partial vertex cover problem on bipartite graphs is open. In this paper, we show that the partial vertex cover problem is NP-hard on bipartite graphs. Then, we show that the budgeted maximum coverage problem (a problem related to partial vertex cover problem) admits an $\frac{8}{9}$-approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.13-26, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_2〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402014
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:40:30
Dernière modification le : vendredi 8 juin 2018 - 18:40:02
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:28:36

Fichier

978-3-662-44602-7_2_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Bugra Caskurlu, Vahan Mkrtchyan, Ojas Parekh, K. Subramani. On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.13-26, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_2〉. 〈hal-01402014〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

166