{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:04:34Z","timestamp":1780632274435,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","award":["HR001123S0001-FP-004"],"award-info":[{"award-number":["HR001123S0001-FP-004"]}],"id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,5]]},"DOI":"10.1007\/s10878-025-01285-4","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T13:41:33Z","timestamp":1745847693000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Analyzing the 3-path vertex cover problem in selected graph classes"],"prefix":"10.1007","volume":"49","author":[{"given":"Sangram K.","family":"Jena","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5821-5117","authenticated-orcid":false,"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"issue":"1\u20132","key":"1285_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"Paola Alimonti","year":"2000","unstructured":"Alimonti Paola, Kann Viggo (2000) Some apx-completeness results for cubic graphs. Theor Comput Sci 237(1\u20132):123\u2013134","journal-title":"Theor Comput Sci"},{"key":"1285_CR2","doi-asserted-by":"crossref","unstructured":"Arora Sanjeev, Lund Carsten, Motwani Rajeev, Sudan Madhu, Szegedy Mario (1992) Proof verification and hardness of approximation problems. In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 14\u201323. IEEE Computer Society","DOI":"10.1109\/SFCS.1992.267823"},{"issue":"12","key":"1285_CR3","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"Bo\u0161tjan Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar Bo\u0161tjan, Kardo\u0161 Franti\u0161ek, Katreni\u010d J\u00e1n, Semani\u0161in Gabriel (2011) Minimum k-path vertex cover. Discr Appl Math 159(12):1189\u20131195","journal-title":"Discr Appl Math"},{"issue":"2","key":"1285_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-005-0649-5","volume":"105","author":"Kathie Cameron","year":"2006","unstructured":"Cameron Kathie, Hell Pavol (2006) Independent packings in structured graphs. Math Prog 105(2):201\u2013213","journal-title":"Math Prog"},{"key":"1285_CR5","unstructured":"Chang Maw-Shang, Chen Li-Hsuan, Hung Ling-Ju, Liu Yi-Zhi, Rossmanith Peter, Sikdar Somnath (2014) An o*(1. 4658n)-time exact algorithm for the maximum bounded-degree-1 set problem. In: Proceedings of the 31st workshop on combinatorial mathematics and computation theory, pages 9\u201318"},{"issue":"1\u20133","key":"1285_CR6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"Golumbic Martin Charles","year":"2000","unstructured":"Charles Golumbic Martin, Moshe Lewenstein (2000) New results on induced matchings. Discr Appl Math 101(1\u20133):157\u2013165","journal-title":"Discr Appl Math"},{"key":"1285_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1701-9","volume-title":"Design and analysis of approximation algorithms","author":"DZ Du","year":"2012","unstructured":"Du DZ, Ko KI, Hu X (2012) Design and analysis of approximation algorithms. Springer, UK"},{"key":"1285_CR8","unstructured":"Gollmann Diete (2005) Protocol analysis for concrete environments. In Roberto Moreno-D\u00edaz, Franz Pichler, and Alexis Quesada-Arencibia, editors, In: Computer Aided Systems Theory - EUROCAST 2005, 10th International Conference on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Spain, February 7-11, 2005, Revised Selected Papers, volume 3643 of Lecture Notes in Computer Science, pages 365\u2013372. Springer"},{"issue":"2","key":"1285_CR9","doi-asserted-by":"publisher","first-page":"377","DOI":"10.7151\/dmgt.1453","volume":"29","author":"Frank G\u00f6ring","year":"2009","unstructured":"G\u00f6ring Frank, Harant Jochen, Rautenbach Dieter, Schiermeyer Ingo (2009) On $${{\\cal{f} }}$$-independence in graphs. Discuss Math Graph Theory 29(2):377\u2013383","journal-title":"Discuss Math Graph Theory"},{"key":"1285_CR10","doi-asserted-by":"publisher","DOI":"10.1201\/9781482246582","volume-title":"Fundamentals of domination in graphs","author":"W Haynes Teresa","year":"2013","unstructured":"Haynes Teresa W, Stephen Hedetniemi, Peter Slater (2013) Fundamentals of domination in graphs. CRC Press"},{"issue":"3","key":"1285_CR11","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"S Hochbaum Dorit","year":"1983","unstructured":"Hochbaum Dorit S (1983) Efficient bounds for the stable set, vertex cover and set packing problems. Discr Appl Math 6(3):243\u2013254","journal-title":"Discr Appl Math"},{"key":"1285_CR12","doi-asserted-by":"crossref","unstructured":"Jena Sangram\u00a0K., Subramani K. (2022) Analyzing the 3-path vertex cover problem in planar bipartite graphs. In Ding-Zhu Du, Donglei Du, Chenchen Wu, and Dachuan Xu, editors, In: Theory and Applications of Models of Computation - 17th Annual Conference, TAMC 2022, Tianjin, China, September 16-18, 2022, Proceedings, volume 13571 of Lecture Notes in Computer Science, pages 103\u2013115. Springer","DOI":"10.1007\/978-3-031-20350-3_10"},{"issue":"13","key":"1285_CR13","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.ipl.2013.04.002","volume":"113","author":"Tu Jianhua","year":"2013","unstructured":"Jianhua Tu, Yang Fengmei (2013) The vertex cover p3 problem in cubic graphs. Inform Process Lett 113(13):481\u2013485","journal-title":"Inform Process Lett"},{"issue":"14","key":"1285_CR14","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"Tu Jianhua","year":"2011","unstructured":"Jianhua Tu, Zhou Wenli (2011) A factor 2 approximation algorithm for the vertex cover p3 problem. Inform Process Lett 111(14):683\u2013686","journal-title":"Inform Process Lett"},{"issue":"50","key":"1285_CR15","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"Tu Jianhua","year":"2011","unstructured":"Jianhua Tu, Zhou Wenli (2011) A primal-dual approximation algorithm for the vertex cover p3 problem. Theor Comput Sci 412(50):7044\u20137048","journal-title":"Theor Comput Sci"},{"issue":"50","key":"1285_CR16","doi-asserted-by":"publisher","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"Franti\u0161ek Kardo\u0161","year":"2011","unstructured":"Kardo\u0161 Franti\u0161ek, Katreni\u010d J\u00e1n, Schiermeyer Ingo (2011) On computing the minimum 3-path vertex cover and dissociation number of graphs. Theor Comput Sci 412(50):7009\u20137017","journal-title":"Theor Comput Sci"},{"key":"1285_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"M Karp Richard","year":"1972","unstructured":"Karp Richard M (1972) Reducibility among combinatorial problems. Complexity of computer computations. Plenum Press, pp 85\u2013103"},{"issue":"2","key":"1285_CR18","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"David Lichtenstein","year":"1982","unstructured":"Lichtenstein David (1982) Planar formulae and their uses. SIAM J Comput 11(2):329\u2013343","journal-title":"SIAM J Comput"},{"issue":"4","key":"1285_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","volume":"88","author":"Vadim Lozin","year":"2003","unstructured":"Lozin Vadim, Rautenbach Dieter (2003) Some results on graphs without long induced paths. Inform Process Lett 88(4):167\u2013171","journal-title":"Inform Process Lett"},{"key":"1285_CR20","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2014.01.019","volume":"526","author":"Kumar Mrinal","year":"2014","unstructured":"Mrinal Kumar, Sounaka Mishra, Safina Devi N, Saket Saurabh (2014) Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization. Theor Comput Sci 526:90\u201396","journal-title":"Theor Comput Sci"},{"key":"1285_CR21","doi-asserted-by":"crossref","unstructured":"Novotn\u1ef3 Mari\u00e1n (2010) Design and analysis of a generalized canvas protocol. In: IFIP International Workshop on Information Security Theory and Practices, pages 106\u2013121","DOI":"10.1007\/978-3-642-12368-9_8"},{"issue":"13","key":"1285_CR22","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","volume":"159","author":"Yury Orlovich","year":"2011","unstructured":"Orlovich Yury, Dolgui Alexandre, Finke Gerd, Gordon Valery, Werner Frank (2011) The complexity of dissociation set problems in graphs. Discr Appl Math 159(13):1352\u20131366","journal-title":"Discr Appl Math"},{"issue":"2","key":"1285_CR23","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"H Papadimitriou Christos","year":"1982","unstructured":"Papadimitriou Christos H, Mihalis Yannakakis (1982) The complexity of restricted spanning tree problems. J ACM (JACM) 29(2):285\u2013309","journal-title":"J ACM (JACM)"},{"issue":"3","key":"1285_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"H Papadimitriou Christos","year":"1991","unstructured":"Papadimitriou Christos H, Mihalis Yannakakis (1991) Optimization, approximation, and complexity classes. J comput Syst Sci 43(3):425\u2013440","journal-title":"J comput Syst Sci"},{"key":"1285_CR25","first-page":"241","volume":"72","author":"Boliac Rodica","year":"2004","unstructured":"Rodica Boliac, Lozin VV, Cameron K (2004) On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combinatoria 72:241\u2013253","journal-title":"Ars Combinatoria"},{"key":"1285_CR26","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.dam.2014.10.033","volume":"184","author":"Devi N Safina","year":"2015","unstructured":"Safina Devi N, Mane Aniket C, Sounaka Mishra (2015) Computational complexity of minimum p4 vertex cover problem for regular and k1, 4-free graphs. Discr Appl Math 184:114\u2013121","journal-title":"Discr Appl Math"},{"key":"1285_CR27","doi-asserted-by":"crossref","unstructured":"Tu Jianhua, Shi Yongtang (2019) An efficient polynomial time approximation scheme for the vertex cover $$p_3$$ problem on planar graphs. Discussiones Mathematicae: Graph Theory, 39(1)","DOI":"10.7151\/dmgt.2060"},{"key":"1285_CR28","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2016.04.043","volume":"657","author":"Mingyu Xiao","year":"2017","unstructured":"Xiao Mingyu, Kou Shaowei (2017) Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theor Comput Sci 657:86\u201397","journal-title":"Theor Comput Sci"},{"issue":"2","key":"1285_CR29","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"Mihalis Yannakakis","year":"1981","unstructured":"Yannakakis Mihalis (1981) Node-deletion problems on bipartite graphs. SIAM J Comput 10(2):310\u2013327","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01285-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01285-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01285-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T15:34:36Z","timestamp":1748014476000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01285-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1285"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01285-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"10 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2025","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 that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"58"}}