×

Maximum weighted independent sets with a budget. (English) Zbl 1485.68187

Gaur, Daya (ed.) et al., Algorithms and discrete applied mathematics. Third international conference, CALDAM 2017, Sancoale, Goa, India, February 16–18, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10156, 254-266 (2017).
Summary: Given a graph \(G\), a non-negative integer \(k\), and a weight function that maps each vertex in \(G\) to a positive real number, the Maximum Weighted Budgeted Independent Set (MWBIS) problem is about finding a maximum weighted independent set in \(G\) of cardinality at most \(k\). A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in \(G\), is called the Maximum Independent Vertex Coverage (MIVC) problem. In other words, the MIVC problem is about finding an independent set of cardinality at most \(k\) with maximum coverage.
J. Håstad [“Clique is hard to approximate within \(n^{1-\epsilon}\)”, in: Proceedings of the 37th annual symposium on foundations of computer science, FOCS 1996. Los Alamitos : IEEE Computer Society. 627–636 (1996)] showed that there is no \(\frac{1}{n^{1-\epsilon}}\)-factor approximation algorithm for the well-known Maximum Weighted Independent Set (MWIS) problem, where \(\epsilon > 0\), assuming NP-hard problems have no randomized polynomial time algorithms. Being a generalization of the MWIS problem, the above-mentioned inapproximability result applies to MWBIS too. Due to the existence of such inapproximability results for MWBIS in general graphs, in this paper, we restrict our study of MWBIS to the class of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits an easy, greedy \(\frac{1}{2}\)-factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. This rules out the possibility of any LP-based algorithm that uses the natural LP relaxation to yield a better factor of approximation.
For the entire collection see [Zbl 1355.68015].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 17–30. Springer, Heidelberg (1999). doi: 10.1007/3-540-48777-8_2 · Zbl 0948.90122 · doi:10.1007/3-540-48777-8_2
[2] Apollonio, N., Simeone, B.: Improved approximation of maximum vertex coverage problem on bipartite graphs. SIAM J. Discret. Math. 28(3), 1137–1151 (2014) · Zbl 1310.90095 · doi:10.1137/130931059
[3] Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discret. Appl. Math. 165, 37–48 (2014) · Zbl 1288.05201 · doi:10.1016/j.dam.2013.05.015
[4] Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pp. 74–80. IEEE (2009) · Zbl 1243.68183 · doi:10.1109/CCC.2009.38
[5] Bandyapadhyay, S.: A variant of the maximum weight independent set problem. CoRR, abs/1409.0173 (2014)
[6] Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137–144 (2001) · Zbl 0974.68236 · doi:10.1006/jagm.2000.1150
[7] Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999). doi: 10.1007/3-540-48523-6_17 · doi:10.1007/3-540-48523-6_17
[8] Boppana, R., Halldórsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT Numer. Math. 32(2), 180–196 (1992) · Zbl 0761.68044 · doi:10.1007/BF01994876
[9] Bshouty, N.H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 298–308. Springer, Heidelberg (1998). doi: 10.1007/BFb0028569 · doi:10.1007/BFb0028569
[10] Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 13–26. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-44602-7_2 · Zbl 1417.68149 · doi:10.1007/978-3-662-44602-7_2
[11] Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004) · Zbl 1068.68177 · doi:10.1016/j.jalgor.2004.04.002
[12] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[13] Halldórsson, M.M.: Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl. 4(1), 1–16 (2000) · Zbl 0952.05069 · doi:10.7155/jgaa.00020
[14] Han, Q., Ye, Y., Zhang, H., Zhang, J.: On approximation of max-vertex-cover. Eur. J. Oper. Res. 143(2), 342–355 (2002) · Zbl 1058.90036 · doi:10.1016/S0377-2217(02)00330-2
[15] Håstad, J.: Clique is hard to approximate within \[ n^{1-\epsilon } \] n 1 - . In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 627–636. IEEE (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.