{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:49:08Z","timestamp":1787323748993,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-1-0199"],"award-info":[{"award-number":["FA9550-12-1-0199"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1305054"],"award-info":[{"award-number":["CCF-1305054"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0849735"],"award-info":[{"award-number":["CNS-0849735"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0827397"],"award-info":[{"award-number":["CCF-0827397"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In this paper, we study two closely related problems on bipartite graphs, viz., the partial vertex cover problem and the budgeted maximum coverage problem. Both these problems arise in a number of different application domains, including, but not limited to, computer security and transportation logistics. It is well known that the vertex cover problem is solvable in polynomial time on bipartite graphs. However, the computational complexity of the partial vertex cover problem on bipartite graphs was open, thus far. In this paper, we establish that the partial vertex cover problem is \\bf NP-hard, even on bipartite graphs. Our result also establishes that the closely related budgeted maximum coverage problem is \\bf NP-hard on bipartite graphs. For the latter problem, we present an $\\frac{8}{9}$-approximation algorithm. Our approximation guarantee matches and resolves the integrality gap of the natural linear programming relaxation for this problem and improves upon a recent $\\frac{4}{5}$-approximation algorithm for the same problem.<\/jats:p>","DOI":"10.1137\/15m1054328","type":"journal-article","created":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T12:18:29Z","timestamp":1505996309000},"page":"2172-2184","source":"Crossref","is-referenced-by-count":11,"title":["Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs"],"prefix":"10.1137","volume":"31","author":[{"given":"Bugra","family":"Caskurlu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahan","family":"Mkrtchyan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ojas","family":"Parekh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"atypb1","first-page":"17","author":"Ageev A. A.","year":"1999","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.05.015"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/130931059"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1150"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00434-9"},{"key":"atypb6","first-page":"298","author":"Bshouty N. H.","year":"1998","journal-title":"Berlin"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.03.012"},{"key":"atypb8","unstructured":"B. Caskurlu and K. Subramani,\n                      On partial vertex cover on Bipartite Graphs and Trees\n                      ,http:\/\/arxiv.org\/abs\/1304.5934, 2013."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"atypb10","first-page":"111","author":"Hochbaum D. S.","year":"1998","journal-title":"NY"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_5"},{"key":"atypb12","first-page":"240","author":"Langer A.","year":"2008","journal-title":"Springer Berlin"},{"key":"atypb13","first-page":"367","author":"Mo\u0308lle D.","year":"2007","journal-title":"Prague"},{"key":"atypb14","first-page":"598","author":"Richter S.","year":"2006","journal-title":"Berlin"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9317-0"},{"key":"atypb16","first-page":"143","volume":"17","author":"Joret G.","year":"2015","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597045"},{"key":"atypb18","first-page":"85","author":"Karp R.","year":"1972","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9003-z"},{"key":"atypb21","first-page":"350","author":"Mkrtchyan V.","year":"2017","journal-title":"Switzerland"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.002"},{"key":"atypb24","first-page":"335","author":"Mestre J.","year":"2007","journal-title":"Berlin"},{"key":"atypb25","first-page":"70","author":"Moss A.","year":"1999","journal-title":"Inform. Process. Lett."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1054328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:13:07Z","timestamp":1787321587000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1054328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1054328"],"URL":"https:\/\/doi.org\/10.1137\/15m1054328","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}