{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T02:09:03Z","timestamp":1758593343946,"version":"3.44.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"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":["Acta Informatica"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s00236-025-00498-8","type":"journal-article","created":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T07:22:37Z","timestamp":1756538557000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized lower bounds for the weighted vertex cover problem in trees"],"prefix":"10.1007","volume":"62","author":[{"given":"P.","family":"Wojciechowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,30]]},"reference":[{"key":"498_CR1","unstructured":"Abu-Khzam, F.\u00a0N., Collins, R.\u00a0L., Fellows, M.\u00a0R., Langston, M.\u00a0A., Suters, W.\u00a0H., Symons, C.\u00a0T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Arge, L., Italiano, G.\u00a0F., Sedgewick, R. (eds.), Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, January 10, pp. 62\u201369. SIAM (2004)"},{"issue":"6","key":"498_CR2","doi-asserted-by":"publisher","first-page":"1159","DOI":"10.1016\/j.jcss.2010.12.002","volume":"77","author":"O Amini","year":"2011","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Implicit branching and parameterized partial cover problems. J. Comput. Syst. Sci. 77(6), 1159\u20131171 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"498_CR3","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"},{"key":"498_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-540-75520-3_31","volume-title":"15th Annual European Symposium on Algorithms","author":"R Bar-Yehuda","year":"2007","unstructured":"Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D.: Approximation of partial capacitated vertex cover. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) 15th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 4698, pp. 335\u2013346. Springer, Eilat, Israel (2007)"},{"issue":"6","key":"498_CR5","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":"498_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"498_CR7","unstructured":"Bodlaender, H.\u00a0L., Jansen, B.\u00a0M.\u00a0P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Schwentick, T., D\u00fcrr, C. (eds.) 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, Dortmund, Germany,\u00a0Vol. 9 of LIPIcs, pp. 165\u2013176. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2011)"},{"key":"498_CR8","unstructured":"Bringmann, K.: Fine-grained complexity theory (tutorial). In: Niedermeier, R., Paul,\u00a0C. (eds.)\u00a036th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, Berlin, Germany, Vol 126 of LIPIcs, pp. 4:1\u20134:7. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"16\u201318","key":"498_CR9","doi-asserted-by":"publisher","first-page":"1855","DOI":"10.1016\/j.tcs.2010.02.005","volume":"411","author":"J Cardinal","year":"2010","unstructured":"Cardinal, J., Hoefer, M.: Non-cooperative facility location and covering games. Theor. Comput. Sci. 411(16\u201318), 1855\u20131876 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"498_CR10","doi-asserted-by":"crossref","unstructured":"Caskurlu, B., Gehani, A., \u00c7agatay Bilgin, C., Subramani, K.: Analytical models for risk-based intrusion response. Comput. Networks\u00a057(10):2181\u20132192 (2013)","DOI":"10.1016\/j.comnet.2013.03.012"},{"issue":"3","key":"498_CR11","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. Discrete Math. 31(3), 2172\u20132184 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"498_CR12","doi-asserted-by":"crossref","unstructured":"Chen, J., Kanj, I.\u00a0A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) Mathematical Foundations of Computer Science, pp. 238\u2013249. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11821069_21"},{"issue":"4","key":"498_CR13","doi-asserted-by":"publisher","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014)","journal-title":"J. ACM"},{"issue":"1","key":"498_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."},{"issue":"4","key":"498_CR15","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"498_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F.\u00a0V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press (2019)","DOI":"10.1017\/9781107415157"},{"issue":"1","key":"498_CR17","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"498_CR18","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"key":"498_CR19","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597045","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G.: A Better Approximation Ratio for the Vertex Cover Problem. ACM Transactions on Algorithms (2009). https:\/\/doi.org\/10.1145\/1597036.1597045","journal-title":"ACM Transactions on Algorithms"},{"key":"498_CR20","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":"498_CR21","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"},{"issue":"4","key":"498_CR22","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489\u2013509 (2011)","journal-title":"Algorithmica"},{"issue":"23\u201324","key":"498_CR23","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/j.ipl.2011.09.003","volume":"111","author":"M Lampis","year":"2011","unstructured":"Lampis, M.: A kernel of order 2 k-c log k for vertex cover. Inf. Process. Lett. 111(23\u201324), 1089\u20131091 (2011)","journal-title":"Inf. Process. Lett."},{"key":"498_CR24","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower Bounds Based on the Exponential Time Hypothesis. Bulletin of the EATCS, 41\u201371 (2011)"},{"issue":"1","key":"498_CR25","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"},{"issue":"1","key":"498_CR26","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.disopt.2010.10.001","volume":"8","author":"N Misra","year":"2011","unstructured":"Misra, N., Raman, V., Saurabh, S.: Lower bounds on kernelization. Discret. Optim. 8(1), 110\u2013128 (2011)","journal-title":"Discret. Optim."},{"issue":"4","key":"498_CR27","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1142\/S0129054123500089","volume":"35","author":"V Mkrtchyan","year":"2024","unstructured":"Mkrtchyan, V., Parekh, O., Subramani, K.: Approximation algorithms for partial vertex covers in trees. Int. J. Found. Comput. Sci. 35(4), 387\u2013407 (2024)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"498_CR28","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/s00224-023-10152-w","volume":"68","author":"V Mkrtchyan","year":"2024","unstructured":"Mkrtchyan, V., Petrosyan, G., Subramani, K., Wojciechowski, P.: On the partial vertex cover problem in bipartite graphs - a parameterized perspective. Theory Comput. Syst. 68(1), 122\u2013143 (2024)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"498_CR29","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"key":"498_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2021.108144","volume":"194","author":"Y Yigit","year":"2021","unstructured":"Yigit, Y., Akram, V.K., Dagdeviren, O.: Breadth-first search tree integrated vertex cover algorithms for link monitoring and routing in wireless sensor networks. Comput. Networks 194, 108144 (2021)","journal-title":"Comput. Networks"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00498-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00498-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00498-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T06:25:59Z","timestamp":1758522359000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00498-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,30]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["498"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00498-8","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,8,30]]},"assertion":[{"value":"30 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2025","order":3,"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"}}],"article-number":"35"}}