{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:32:36Z","timestamp":1771651956986,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["P2EZP2-191861"],"award-info":[{"award-number":["P2EZP2-191861"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We combine both techniques, in order to better classify the complexity of problems in the parameterized setting. Specifically, we see that some problems in the class of compositional problems, which do not have polynomial kernels under standard complexity-theoretic assumptions, do have polynomial kernels under the reoptimization model for some local modifications. We also observe that, for some other local modifications, these same problems do not have polynomial kernels unless <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbf{NP}\\subseteq \\mathbf{coNP\/poly}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>NP<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>coNP<\/mml:mi>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>poly<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We find examples of compositional problems, whose reoptimization versions do not have polynomial kernels under any of the considered local modifications. Finally, in another negative result, we prove that the reoptimization version of <jats:sc>Connected Vertex Cover<\/jats:sc> does not have a polynomial kernel unless <jats:sc>Set Cover<\/jats:sc> has a polynomial compression. In a different direction, looking at problems with polynomial kernels, we find that the reoptimization version of <jats:sc>Vertex Cover<\/jats:sc> has a polynomial kernel of size <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{2k+1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.<\/jats:p>","DOI":"10.1007\/s00236-022-00428-y","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T07:26:00Z","timestamp":1658733960000},"page":"427-450","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reoptimization of parameterized problems"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9164-3674","authenticated-orcid":false,"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6161-7440","authenticated-orcid":false,"given":"Elisabet","family":"Burjons","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3018-2557","authenticated-orcid":false,"given":"Martin","family":"Raszyk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0177-8028","authenticated-orcid":false,"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,25]]},"reference":[{"key":"428_CR1","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, F.N., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: On the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607, 426\u2013434 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"428_CR2","unstructured":"Alman, J., Mnich, M., Williams, V.V.: Dynamic parameterized problems and algorithms. In: Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP\u00a02017), LIPiCS. Dagstuhl Publishing, pp.\u00a041:1\u201341:16 (2017)"},{"issue":"3","key":"428_CR3","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"FN Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, H.W.: Crown structures for vertex cover kernelization. Theory Comput. Syst. 41(3), 411\u2013430 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"428_CR4","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1002\/net.10091","volume":"42","author":"C Archetti","year":"2003","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"428_CR5","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT\u00a02006), LNCS 4059, pp.\u00a0196\u2013207. Springer (2006)","DOI":"10.1007\/11785293_20"},{"key":"428_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Forlizzi, L., Hromkovi\u010d, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances. In: Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (IFIP TCS\u00a02006), pp.\u00a0251\u2013270 (2006)","DOI":"10.1007\/978-0-387-34735-6_21"},{"key":"428_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u00a02008) (LNCS 4910), pp.\u00a050\u201365. Springer (2008)","DOI":"10.1007\/978-3-540-77566-9_5"},{"issue":"8","key":"428_CR8","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":"35","key":"428_CR9","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"428_CR10","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"key":"428_CR11","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Deterministic Parameterized Connected Vertex Cover. In: Proceedings of the Algorithm Theory (SWAT\u00a02012), pp.\u00a095\u2013106. Springer (2012)","DOI":"10.1007\/978-3-642-31155-0_9"},{"key":"428_CR12","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 (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"428_CR13","doi-asserted-by":"crossref","unstructured":"Daligault, J., Thomass\u00e9, S.: On finding directed trees with many leaves. In: Parameterized and Exact Computation, pp.\u00a086\u201397, Springer (2009)","DOI":"10.1007\/978-3-642-11269-0_7"},{"issue":"2","key":"428_CR14","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-13:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"428_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."},{"issue":"1","key":"428_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"428_CR17","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"428_CR18","doi-asserted-by":"crossref","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. In: 53rd Annual Symposium on Foundations of Computer Science (IEEE\u00a02012), pp.\u00a0609\u2013618 (2012)","DOI":"10.1109\/FOCS.2012.71"},{"key":"428_CR19","first-page":"38:1","volume":"8","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Trans. Algorithms 8, 38:1-38:19 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"428_CR20","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer (2006)"},{"issue":"1","key":"428_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2012.03.004","volume":"79","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Thomass\u00e9, S.: A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci. 79(1), 1\u20136 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"428_CR22","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.\u00a0H.\u00a0Freeman & Co., (1990)"},{"key":"428_CR23","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Kratsch, S., So\u0142tys, K., Wahlstr\u00f6m, M., Wu, X.: A Completeness Theory for Polynomial (Turing) Kernelization. Parameterized and Exact Computation, pp. 202\u2013215, Springer (2013)","DOI":"10.1007\/978-3-319-03898-8_18"},{"issue":"9","key":"428_CR24","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":"428_CR25","doi-asserted-by":"crossref","unstructured":"Li, W., Wang, J., Chen, J., Cao, Y.: A 2k-vertex kernel for maximum internal spanning tree. In: Proceedings of Algorithms and Data Structures (WADS 2015), LNCS 9214, pp. 495\u2013505. Springer (2015)","DOI":"10.1007\/978-3-319-21840-3_41"},{"key":"428_CR26","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2018.05.004","volume":"739","author":"W Li","year":"2018","unstructured":"Li, W., Zhu, B.: A $$2k$$-kernelization algorithm for vertex cover based on crown decomposition. Theor. Comput. Sci. 739, 80\u201385 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"428_CR27","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"issue":"1","key":"428_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-010-0973-2","volume":"27","author":"K Ozeki","year":"2011","unstructured":"Ozeki, K., Yamashita, T.: Spanning trees: a survey. Graphs Combin. 27(1), 1\u201326 (2011)","journal-title":"Graphs Combin."},{"issue":"4","key":"428_CR29","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"428_CR30","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: A theory and algorithms for combinatorial reoptimization. In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), LNCS 7256, pp.\u00a0618\u2013630. Springer (2012)","DOI":"10.1007\/978-3-642-29344-3_52"},{"issue":"1","key":"428_CR31","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"MW Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math. 72(1), 155\u2013166 (1997)","journal-title":"Discrete Appl. Math."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00428-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00428-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00428-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:08:51Z","timestamp":1661591331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00428-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,25]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["428"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00428-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,25]]},"assertion":[{"value":"28 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None of the authors declare any conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}