{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T03:45:14Z","timestamp":1783741514734,"version":"3.55.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T00:00:00Z","timestamp":1651190400000},"content-version":"vor","delay-in-days":28,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI\/369-18"],"award-info":[{"award-number":["NI\/369-18"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The NP-complete <jats:sc>Vertex Cover<\/jats:sc> problem asks to cover all edges of a graph by a small (given) number of vertices. It is among the most prominent graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-called layers, over the same vertex set but, over time, changing edge sets), we initiate the study of <jats:sc>Multistage Vertex Cover<\/jats:sc>. Herein, given a temporal graph, the goal is to find for each layer of the temporal graph a small vertex cover <jats:italic>and<\/jats:italic> to guarantee that two vertex cover sets of every two consecutive layers differ not too much (specified by a given parameter). We show that, different from classic <jats:sc>Vertex Cover<\/jats:sc> and some other dynamic or temporal variants of it, <jats:sc>Multistage Vertex Cover<\/jats:sc> is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of themost natural parameterizations.<\/jats:p>","DOI":"10.1007\/s00224-022-10069-w","type":"journal-article","created":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T07:02:53Z","timestamp":1651215773000},"page":"454-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Multistage Vertex Cover"],"prefix":"10.1007","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2203-4386","authenticated-orcid":false,"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1703-1236","authenticated-orcid":false,"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valentin","family":"Rohm","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9846-0600","authenticated-orcid":false,"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,29]]},"reference":[{"key":"10069_CR1","unstructured":"Fluschnik, T, Niedermeier, R, Rohm, V, Zschoche, P: Multistage vertex cover. In: Proceeding of 14th IPEC, LIPIcs, vol. 148, pp 14:1\u201314:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"10069_CR2","doi-asserted-by":"publisher","unstructured":"Bampis, E, Escoffier, B, Lampis, M, Paschos, VT: Multistage matchings. In: Proc. of 16th SWAT, of LIPIcs Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 101, pp 7:1\u20137:13 (2018), https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.7","DOI":"10.4230\/LIPIcs.SWAT.2018.7"},{"key":"10069_CR3","doi-asserted-by":"publisher","unstructured":"Gupta, A, Talwar, K, Wieder, U: Changing bases: Multistage optimization for matroids and matchings. In: Proc. of 41st ICALP, of LNCS, Springer, vol. 8572, pp 563\u2013575 (2014), https:\/\/doi.org\/10.1007\/978-3-662-43948-7_47","DOI":"10.1007\/978-3-662-43948-7_47"},{"key":"10069_CR4","doi-asserted-by":"publisher","unstructured":"Bampis, E, Escoffier, B, Teiller, A: Multistage knapsack. In Proc. of 44th MFCS of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 138, pp 22:1\u201322:14 (2022), https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.22","DOI":"10.4230\/LIPIcs.MFCS.2019.22"},{"key":"10069_CR5","doi-asserted-by":"publisher","unstructured":"Eisenstat, D, Mathieu, C, Schabanel, N: Facility location in evolving metrics. In: Proc. of 41st ICALP, LNCS, Springer, pp 459\u2013470 (2014), https:\/\/doi.org\/10.1007\/978-3-662-43951-7_39","DOI":"10.1007\/978-3-662-43951-7_39"},{"key":"10069_CR6","doi-asserted-by":"publisher","unstructured":"Bampis, E, Escoffier, B, Kononov, AV: LP-based algorithms for multistage minimization problems. In: Proc. of 18th WAOA, LNCS, Springer, vol. 12806, pp 1\u201315 (2020), https:\/\/doi.org\/10.1007\/978-3-030-80879-2_1","DOI":"10.1007\/978-3-030-80879-2_1"},{"key":"10069_CR7","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2021.04.002","volume":"868","author":"K Heeger","year":"2021","unstructured":"Heeger, K, Himmel, A-S, Kammer, F, Niedermeier, R, Renken, M, Sajenko, A: Multistage graph problems on a global budget. Theor. Comput. Sci. 868, 46\u201364 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.04.002","journal-title":"Theor. Comput. Sci."},{"key":"10069_CR8","doi-asserted-by":"publisher","unstructured":"Fluschnik, T, Niedermeier, R, Schubert, C, Zschoche, P: Multistage s-t path: Confronting similarity with dissimilarity in temporal graphs. In: Proc. of 31st ISAAC, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 181, pp 43:1\u201343:16. dagstuhl (2020), https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.43","DOI":"10.4230\/LIPIcs.ISAAC.2020.43"},{"key":"10069_CR9","doi-asserted-by":"publisher","unstructured":"Chimani, M, Troost, N, Wiedera, T: Approximating multistage matching problems. In: Proc. of 32nd IWOCA, LNCS, Springer, pp 558\u2013570 (2021), https:\/\/doi.org\/10.1007\/978-3-030-79987-8_39","DOI":"10.1007\/978-3-030-79987-8_39"},{"key":"10069_CR10","doi-asserted-by":"publisher","unstructured":"Fluschnik, T: A multistage view on 2-satisfiability of LNCS, Springer, vol. 12701, pp 231\u2013244 (2021), https:\/\/doi.org\/10.1007\/978-3-030-75242-2_16","DOI":"10.1007\/978-3-030-75242-2_16"},{"issue":"8","key":"10069_CR11","doi-asserted-by":"publisher","first-page":"2374","DOI":"10.1007\/s00453-021-00834-7","volume":"83","author":"E Bampis","year":"2021","unstructured":"Bampis, E, Escoffier, B, Schewior, K, Teiller, A: Online multistage subset maximization problems. Algorithmica 83(8), 2374\u20132399 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00834-7","journal-title":"Algorithmica"},{"key":"10069_CR12","unstructured":"Bredereck, R, Fluschnik, T, Kaczmarczyk, A: Multistage committee election. CoRR abs\/2005. 02300, arXiv:https:\/\/arxiv.org\/abs\/2005.02300 (2020)"},{"key":"10069_CR13","doi-asserted-by":"publisher","unstructured":"Kellerhals, L, Renken, M, Zschoche, P: Parameterized algorithms for diverse multistage problems. In: Proc. of 29th ESA of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 204, pp 55:1\u201355:17 (2021), https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.55","DOI":"10.4230\/LIPIcs.ESA.2021.55"},{"key":"10069_CR14","unstructured":"Fluschnik, T, Kunz, P: Bipartite temporal graphs and the parameterized complexity of multistage 2-coloring. CoRR abs\/2111.09049, arXiv:https:\/\/arxiv.org\/abs\/2111.09049 (2021)"},{"key":"10069_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S, Niedermeier, R: Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"10069_CR16","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, FN, Egan, J, Fellows, MR, Rosamond, FA, Shaw, P: On the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607, 426\u2013434 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.06.053","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10069_CR17","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A, Flocchini, P, Quattrociocchi, W, Santoro, N: Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27(5), 387\u2013408 (2012). https:\/\/doi.org\/10.1080\/17445760.2012.668546","journal-title":"International Journal of Parallel, Emergent and Distributed Systems"},{"key":"10069_CR18","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","volume":"806","author":"T Fluschnik","year":"2020","unstructured":"Fluschnik, T, Molter, H, Niedermeier, R, Renken, M, Zschoche, P: Temporal graph classes: A view through temporal separators. Theor. Comput. Sci. 806, 197\u2013218 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"10069_CR19","doi-asserted-by":"crossref","unstructured":"Iwata, Y, Oka, K: Fast dynamic graph algorithms for parameterized problems. In: Proc. of 12th SWAT of LNCS, Springer, vol. 8503, pp 241\u2013252 (2014)","DOI":"10.1007\/978-3-319-08404-6_21"},{"issue":"4","key":"10069_CR20","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/3395037","volume":"16","author":"J Alman","year":"2020","unstructured":"Alman, J, Mnich, M, Williams, VV: Dynamic parameterized problems and algorithms. ACM T. Algorithms 16(4), 45:1\u201345:46, (2020). https:\/\/doi.org\/10.1145\/3395037","journal-title":"ACM T. Algorithms"},{"key":"10069_CR21","doi-asserted-by":"publisher","unstructured":"Chitnis, R, Cormode, G, Esfandiari, H, Hajiaghayi, M, McGregor, A, Monemizadeh, M, Vorotnikova, S: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: Proc. of 27th SODA, SIAM, pp 1326\u20131344 (2016), https:\/\/doi.org\/10.1137\/1.9781611974331.ch92","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"10069_CR22","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida, EC, Mertzios, GB, Spirakis, PG, Zamaraev, V: Temporal vertex cover with a sliding time window. J. Comput. Syst. Sci. 107, 108\u2013123 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2019.08.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"12-14","key":"10069_CR23","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T, Demaine, ED, Harvey, NJA, Papadimitriou, CH, Sideri, M, Uehara, R, Uno, Y: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12-14), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"10069_CR24","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P, Kolaitis, PG, Maneva, E, Papadimitriou, CH: The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10069_CR25","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2017","unstructured":"Mouawad, AE, Nishimura, N, Raman, V, Simjour, N, Suzuki, A: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274\u2013297 (2017)","journal-title":"Algorithmica"},{"issue":"2","key":"10069_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.3390\/a11020020","volume":"11","author":"A Mouawad","year":"2018","unstructured":"Mouawad, A, Nishimura, N, Raman, V, Siebertz, S: Vertex cover reconfiguration and beyond. Algorithms 11(2), 20 (2018)","journal-title":"Algorithms"},{"issue":"9","key":"10069_CR27","doi-asserted-by":"publisher","first-page":"2637","DOI":"10.1007\/s00453-017-0349-6","volume":"80","author":"R Krithika","year":"2018","unstructured":"Krithika, R, Sahu, A, Tale, P: Dynamic parameterized problems. Algorithmica 80(9), 2637\u20132655 (2018)","journal-title":"Algorithmica"},{"key":"10069_CR28","doi-asserted-by":"crossref","unstructured":"Diestel, R: Graph theory. GTM, 5th edn., vol. 173. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53622-3_7"},{"issue":"20","key":"10069_CR29","doi-asserted-by":"publisher","first-page":"2742","DOI":"10.1016\/j.disc.2010.05.028","volume":"310","author":"H Fleischner","year":"2010","unstructured":"Fleischner, H, Sabidussi, G, Sarvanov, VI: Maximum independent sets in 3- and 4-regular Hamiltonian graphs. Discrete Math. 310(20), 2742\u20132749 (2010)","journal-title":"Discrete Math."},{"key":"10069_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, RG, Fellows, MR: Parameterized complexity. Monographs in Computer Science. Springer, Berlin (1999)"},{"issue":"8","key":"10069_CR31","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, HL, Downey, RG, Fellows, MR, Hermelin, D: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009). https:\/\/doi.org\/10.1016\/j.jcss.2009.04.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"10069_CR32","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). https:\/\/doi.org\/10.1137\/130927115","journal-title":"SIAM J. Comput."},{"key":"10069_CR33","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C-K Yap","year":"1983","unstructured":"Yap, C-K: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10069_CR34","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, MR, Johnson, DS, Stockmeyer, LJ: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10069-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10069-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10069-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T09:03:54Z","timestamp":1663923834000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10069-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10069"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10069-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]},"assertion":[{"value":"2 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of this paper was updated to add the missing compact agreement Open Access funding note.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}