{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T21:17:40Z","timestamp":1772831860507,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00453-020-00708-4","type":"journal-article","created":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T03:57:30Z","timestamp":1587787050000},"page":"2902-2926","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the Approximate Compressibility of Connected Vertex Cover"],"prefix":"10.1007","volume":"82","author":[{"given":"Diptapriyo","family":"Majumdar","sequence":"first","affiliation":[]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,25]]},"reference":[{"issue":"8","key":"708_CR1","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"708_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"10","key":"708_CR3","doi-asserted-by":"publisher","first-page":"4043","DOI":"10.1007\/s00453-018-0468-8","volume":"81","author":"M Bougeret","year":"2019","unstructured":"Bougeret, M., Sau, I.: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? Algorithmica 81(10), 4043\u20134068 (2019)","journal-title":"Algorithmica"},{"issue":"4","key":"708_CR4","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Cornell","year":"2005","unstructured":"Cornell, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"key":"708_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Elsevier and MIT Press, pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"708_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"4","key":"708_CR7","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/j.dam.2008.08.026","volume":"157","author":"B Courcelle","year":"2009","unstructured":"Courcelle, B., Kant\u00e9, M.M.: Graph operations characterizing rank-width. Discrete Appl. Math. 157(4), 627\u2013640 (2009)","journal-title":"Discrete Appl. Math."},{"key":"708_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"1","key":"708_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00224-013-9480-1","volume":"54","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. Theory Comput. Syst. 54(1), 73\u201382 (2014)","journal-title":"Theory Comput. Syst."},{"key":"708_CR10","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 68\u201381 (2012)"},{"issue":"4","key":"708_CR11","doi-asserted-by":"publisher","first-page":"23:1","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":"2","key":"708_CR12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"708_CR13","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"issue":"5","key":"708_CR14","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/130927115","volume":"44","author":"A Drucker","year":"2015","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443\u20131479 (2015)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"708_CR15","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B Escoffier","year":"2010","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algorithms 8(1), 36\u201349 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"708_CR16","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"708_CR17","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"key":"708_CR18","unstructured":"Fomin, F.V., Str\u00f8mme. T.J.F.: Vertex cover structural parameterization revisited. In: Graph-Theoretic Concepts in Computer Science\u201442nd International Workshop, WG 2016, Istanbul, Turkey, June 22\u201324, 2016, Revised Selected Papers, pp. 171\u2013182 (2016)"},{"issue":"1","key":"708_CR19","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"708_CR20","volume-title":"Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, vol 57)","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, vol 57). North-Holland, Amsterdam (2004)"},{"issue":"3","key":"708_CR21","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/s00453-014-9910-8","volume":"71","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Wahlstr\u00f6m, M., Xi, W.: A completeness theory for polynomial (turing) kernelization. Algorithmica 71(3), 702\u2013730 (2015)","journal-title":"Algorithmica"},{"key":"708_CR22","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 104\u2013113 (2012)"},{"key":"708_CR23","unstructured":"Hols, E.-M.C., Kratsch, S.: Smaller parameters for vertex cover kernelization. In: 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6\u20138, 2017, Vienna, Austria (2017)"},{"issue":"2","key":"708_CR24","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-012-9393-4","volume":"53","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited\u2014upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"708_CR25","doi-asserted-by":"publisher","first-page":"2258","DOI":"10.1137\/17M112035X","volume":"32","author":"BMP Jansen","year":"2018","unstructured":"Jansen, B.M.P., Pilipczuk, M.: Approximation and kernelization for chordal vertex deletion. SIAM J. Discrete Math. 32(3), 2258\u20132301 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"708_CR26","first-page":"2014","volume":"113","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S.: Recent developments in kernelization: a survey. Bull. EATCS 113, 2014 (2014)","journal-title":"Bull. EATCS"},{"issue":"3","key":"708_CR27","doi-asserted-by":"publisher","first-page":"1806","DOI":"10.1137\/16M1104585","volume":"32","author":"S Kratsch","year":"2018","unstructured":"Kratsch, S.: A randomized polynomial kernelization for vertex cover with a smaller parameter. SIAM J. Discrete Math. 32(3), 1806\u20131839 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"708_CR28","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. J. ACM (Accepted to, 2020)","DOI":"10.1145\/3390887"},{"key":"708_CR29","unstructured":"Krithika, R., Majumdar, D., Raman, V.: Revisiting connected vertex cover: FPT algorithms and lossy kernels. CoRR, arXiv:abs\/1711.07872 (2017)"},{"issue":"8","key":"708_CR30","doi-asserted-by":"publisher","first-page":"1690","DOI":"10.1007\/s00224-017-9837-y","volume":"62","author":"R Krithika","year":"2018","unstructured":"Krithika, R., Majumdar, D., Raman, V.: Revisiting connected vertex cover: FPT algorithms and lossy kernels. Theory Comput. Syst. 62(8), 1690\u20131714 (2018)","journal-title":"Theory Comput. Syst."},{"key":"708_CR31","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization\u2014preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pp. 129\u2013161 (2012)","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"708_CR32","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19\u201323, 2017, pp. 224\u2013237, (2017)"},{"issue":"8","key":"708_CR33","doi-asserted-by":"publisher","first-page":"1910","DOI":"10.1007\/s00224-018-9858-1","volume":"62","author":"D Majumdar","year":"2018","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Polynomial kernels for vertex cover parameterized by small degree modulators. Theory Comput. Syst. 62(8), 1910\u20131951 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"708_CR34","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"708_CR35","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"CD Savage","year":"1982","unstructured":"Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14, 233\u2013237 (1982)","journal-title":"Inf. Process. Lett."},{"key":"708_CR36","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"708_CR37","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00708-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00708-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00708-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T10:24:52Z","timestamp":1619346292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00708-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,25]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["708"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00708-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,25]]},"assertion":[{"value":"16 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}