{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T14:22:01Z","timestamp":1758637321228},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s00224-023-10152-w","type":"journal-article","created":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T02:02:03Z","timestamp":1701396123000},"page":"122-143","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective"],"prefix":"10.1007","volume":"68","author":[{"given":"Vahan","family":"Mkrtchyan","sequence":"first","affiliation":[]},{"given":"Garik","family":"Petrosyan","sequence":"additional","affiliation":[]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[]},{"given":"Piotr","family":"Wojciechowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,1]]},"reference":[{"key":"10152_CR1","doi-asserted-by":"crossref","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Implicit branching and parameterized partial cover problems. J. Comp. Sys. Sciences (77), 1159\u20131171 (2011)","DOI":"10.1016\/j.jcss.2010.12.002"},{"key":"10152_CR2","doi-asserted-by":"crossref","unstructured":"Ageev A.A., Sviridenko M.: Approximation algorithms for maximum coverage and max cut with given size of parts. IPCO, pp. 17\u201330 (1999)","DOI":"10.1007\/3-540-48777-8_2"},{"issue":"1\u20132","key":"10152_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"10152_CR4","doi-asserted-by":"crossref","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discrete Appl. Math. (165), 37\u201348 (2014)","DOI":"10.1016\/j.dam.2013.05.015"},{"issue":"3","key":"10152_CR5","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1137\/130931059","volume":"28","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: Improved approximation of maximum vertex coverage problem on bipartite graphs. SIAM J. Discrete Math. 28(3), 1137\u20131151 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10152_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"issue":"10","key":"10152_CR7","first-page":"2181","volume":"57","author":"CC Bilgin","year":"2013","unstructured":"Bilgin, C.C., Caskurlu, B., Gehani, A., Subramani, K.: Analytical models for risk-based intrusion response. Computer Networks (Special issue on Security\/Identity Architecture) 57(10), 2181\u20132192 (2013)","journal-title":"Computer Networks (Special issue on Security\/Identity Architecture)"},{"issue":"6","key":"10152_CR8","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser, M.: Computing small partial coverings. Inf. Process. Lett. 85(6), 327\u2013331 (2003)","journal-title":"Inf. Process. Lett."},{"key":"10152_CR9","doi-asserted-by":"crossref","unstructured":"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 STACS, pp. 298\u2013308 (1998)","DOI":"10.1007\/BFb0028569"},{"issue":"3","key":"10152_CR10","doi-asserted-by":"publisher","first-page":"2172","DOI":"10.1137\/15M1054328","volume":"31","author":"B Caskurlu","year":"2017","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: Partial vertex cover and budgeted maximum coverage in bipartite graphs. SIAM J. Disc. Math. 31(3), 2172\u20132184 (2017)","journal-title":"SIAM J. Disc. Math."},{"key":"10152_CR11","doi-asserted-by":"crossref","unstructured":"Caskurlu B., Mkrtchyan V., Parekh O., Subramani K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. IFIP TCS, pp. 13\u201326 (2014)","DOI":"10.1007\/978-3-662-44602-7_2"},{"issue":"4","key":"10152_CR12","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.jcss.2003.09.003","volume":"67","author":"J Chen","year":"2003","unstructured":"Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. J. Comput. Syst. Sci. 67(4), 833\u2013847 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"10152_CR13","doi-asserted-by":"crossref","unstructured":"Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S.: Parameterized algorithms. Springer, pp. 3\u2013555 (2015)","DOI":"10.1007\/978-3-319-21275-3_1"},{"issue":"1","key":"10152_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. of Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. of Math."},{"key":"10152_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00317-9","volume":"191","author":"R Downey","year":"1998","unstructured":"Downey, R., Fellows, M., Regan, K.: Parameterized circuit complexity and the W hierarchy. Theoret. Comput. Sci. 191, 97\u2013115 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"10152_CR16","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10152_CR17","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1125994.1125998","volume":"2","author":"R Hassin","year":"2006","unstructured":"Hassin, R., Levin, A.: The minimum generalized vertex cover problem. ACM Trans. Algorithms 2(1), 66\u201378 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"10152_CR18","doi-asserted-by":"crossref","unstructured":"Hochbaum D.S.: The $$t$$-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of APPROX, pp. 111\u2013122 (1998)","DOI":"10.1007\/BFb0053968"},{"issue":"2","key":"10152_CR19","first-page":"143","volume":"17","author":"G Joret","year":"2015","unstructured":"Joret, G., Vetta, A.: Reducing the rank of a matroid. Disc. Math. and Theor. Comp. Sci. 17(2), 143\u2013156 (2015)","journal-title":"Disc. Math. and Theor. Comp. Sci."},{"issue":"4","key":"10152_CR20","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms 5(4), 41:1-41:8 (2009)","journal-title":"ACM Transactions on Algorithms"},{"key":"10152_CR21","doi-asserted-by":"crossref","unstructured":"Karp R.: Reducibility among combinatorial problems. In: Miller R., Thatcher J. (eds.), Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10152_CR22","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. (74), 335\u2013349 (2008)","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"10152_CR23","unstructured":"Khot S., Minzer D., Safra M.: Pseudorandom sets in grassmann graph have near-perfect expansion. Electronic colloquium on computational complexity, Report No. 6 (2018)"},{"issue":"1","key":"10152_CR24","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"S Khuller","year":"2004","unstructured":"Khuller, S., Gandhi, R., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"10152_CR25","doi-asserted-by":"crossref","unstructured":"Langer A., Kneis J., Rossmanith P.: Improved upper bounds for partial vertex cover. In: WG, pp. 240\u2013251 (2008)","DOI":"10.1007\/978-3-540-92248-3_22"},{"issue":"1","key":"10152_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-007-9003-z","volume":"55","author":"J Mestre","year":"2009","unstructured":"Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica 55(1), 227\u2013239 (2009)","journal-title":"Algorithmica"},{"key":"10152_CR27","doi-asserted-by":"crossref","unstructured":"Mestre, J., Bar-Yehuda, R., Flysher, G., Rawitz, D.: Approximation of partial capacitated vertex cover. Lect. Notes Comput. Sci. (4698), 335\u2013346 (2007)","DOI":"10.1007\/978-3-540-75520-3_31"},{"key":"10152_CR28","doi-asserted-by":"crossref","unstructured":"Mkrtchyan V., Parekh O., Segev D., Subramani K.: The approximability of partial vertex covers in trees. In: SOFSEM, Limerick, Ireland, pp. 350\u2013360 (2017)","DOI":"10.1007\/978-3-319-51963-0_27"},{"key":"10152_CR29","doi-asserted-by":"crossref","unstructured":"Mkrtchyan V., Petrosyan G., Subramani K., Wojciechowski P.: Parameterized algorithms for partial vertex covers in bipartite graphs. In: IWOCA, pp. 395\u2013408 (2020)","DOI":"10.1007\/978-3-030-48966-3_30"},{"issue":"1","key":"10152_CR30","doi-asserted-by":"publisher","first-page":"91","DOI":"10.7155\/jgaa.00584","volume":"26","author":"V Mkrtchyan","year":"2022","unstructured":"Mkrtchyan, V., Petrosyan, G.: On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs. J. Graph Algorithms Appl. 26(1), 91\u2013110 (2022)","journal-title":"J. Graph Algorithms Appl."},{"key":"10152_CR31","doi-asserted-by":"crossref","unstructured":"M\u00f6lle D., Kneis J., Rossmanith P.: Partial vs. complete domination: $$t$$-dominating set. In: SOFSEM (1), pp. 367\u2013376 (2007)","DOI":"10.1007\/978-3-540-69507-3_31"},{"key":"10152_CR32","doi-asserted-by":"crossref","unstructured":"Moss A., Khuller S., (Seffi) Naor J.: The budgeted maximum coverage problem. Inform. Process. Lett. 70(1), 39\u201345 (1999)","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"10152_CR33","doi-asserted-by":"crossref","unstructured":"Niedermeier, R., Guo, J., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. Lect. Notes Comput. Sci. (3608), 36\u201348 (2005)","DOI":"10.1007\/11534273_5"},{"key":"10152_CR34","unstructured":"Orponen P., Mannila H.: On approximation preserving reductions: complete problems and robust measures. Technical report, Department of Computer Science, University of Helsinki (1987)"},{"issue":"3","key":"10152_CR35","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"ChH Papadimitriou","year":"1991","unstructured":"Papadimitriou, Ch.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"10152_CR36","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"O Parekh","year":"2011","unstructured":"Parekh, O., K\u00f6nemann, J., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489\u2013509 (2011)","journal-title":"Algorithmica"},{"key":"10152_CR37","doi-asserted-by":"crossref","unstructured":"Richter S., Kneis J., M\u00f6lle D., Rossmanith P.: Intuitive algorithms and $$t$$-vertex cover. In: ISAAC, pp. 598\u2013607 (2006)","DOI":"10.1007\/11940128_60"},{"key":"10152_CR38","doi-asserted-by":"crossref","unstructured":"Stege U., van Rooij I., Hertel A., Hertel P.: An $$O(pn + 1.151^p)$$-algorithm for p-profit cover and its practical implications for vertex cover. In: ISAAC, pp. 249\u2013261 (2002)","DOI":"10.1007\/3-540-36136-7_23"},{"key":"10152_CR39","unstructured":"Paschos V.Th.: A polynomial time approximation schema for max $$k-$$vertex cover in bipartite graphs. arXiv:1909.08435v1 (2019)"},{"key":"10152_CR40","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer-Verlag, New York Inc., New York, NY, USA (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10152-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10152-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10152-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T11:05:02Z","timestamp":1706785502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10152-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10152"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10152-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,1]]},"assertion":[{"value":"30 October 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}