{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:53:57Z","timestamp":1754600037276,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007210","name":"RWTH Aachen University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007210","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"abstract":"Abstract<\/jats:title>In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class $$\\Pi $$<\/jats:tex-math>\n \u03a0<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> at all times. We consider only hereditary properties\u00a0$$\\Pi $$<\/jats:tex-math>\n \u03a0<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs\u00a0$${{\\mathcal{F}}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed<\/jats:sc> Connected<\/jats:sc>$${{\\mathcal{F}}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Node<\/jats:sc>-Deletion<\/jats:sc> Problem<\/jats:sc>, where all graphs of the family $${\\mathcal{F}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> have to be connected and almost tight lower and upper bounds for the Delayed<\/jats:sc>$$H$$<\/jats:tex-math>\n H<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Node<\/jats:sc>-Deletion<\/jats:sc> Problem<\/jats:sc>, where there is one forbidden induced subgraph H<\/jats:italic> that may be connected or not. For the Delayed<\/jats:sc>$$H$$<\/jats:tex-math>\n H<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Node<\/jats:sc>-Deletion<\/jats:sc> Problem<\/jats:sc> the advice complexity is basically an easy function of the size of the biggest component in\u00a0H<\/jats:italic>. Additionally, we give tight bounds on the Delayed<\/jats:sc> Connected<\/jats:sc>$${\\mathcal{F}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Edge<\/jats:sc>-Deletion<\/jats:sc> Problem<\/jats:sc>, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from\u00a0$${\\mathcal{F}}$$<\/jats:tex-math>\n F<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We give a separate analysis for the Delayed<\/jats:sc> Connected<\/jats:sc>$$H$$<\/jats:tex-math>\n H<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Edge<\/jats:sc>-Deletion<\/jats:sc> Problem<\/jats:sc>, which is less general but admits a bound that is easier to compute.<\/jats:p>","DOI":"10.1007\/s00453-021-00840-9","type":"journal-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:02:41Z","timestamp":1625079761000},"page":"2719-2753","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Online Node- and Edge-Deletion Problems with Advice"],"prefix":"10.1007","volume":"83","author":[{"given":"Li-Hsuan","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5013-8831","authenticated-orcid":false,"given":"Henri","family":"Lotze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"issue":"2","key":"840_CR1","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H Bandelt","year":"1986","unstructured":"Bandelt, H., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory, Ser. B 41(2), 182\u2013208 (1986). https:\/\/doi.org\/10.1016\/0095-8956(86)90043-2","journal-title":"J. Comb. Theory, Ser. B"},{"key":"840_CR2","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H., Hromkovi\u010d, J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the power of randomness versus advice in online computation. In: H.\u00a0Bordihn, M.\u00a0Kutrib, B.\u00a0Truthe (eds.) Languages Alive\u2014Essays Dedicated to J\u00fcrgen Dassow on the Occasion of His 65th Birthday, Lecture Notes in Computer Science, vol. 7300, pp. 30\u201343. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-31644-9_2","DOI":"10.1007\/978-3-642-31644-9_2"},{"key":"840_CR3","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16\u201318, 2009. Proceedings, pp. 331\u2013340 (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_35","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"840_CR4","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2017.03.001","volume":"254","author":"H B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: Online algorithms with advice: the tape model. Inf. Comput. 254, 59\u201383 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.03.001","journal-title":"Inf. Comput."},{"key":"840_CR5","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the advice complexity of the knapsack problem. In: D. Fern\u00e1ndez-Baca (ed.) LATIN 2012: Theoretical Informatics\u201410th Latin American Symposium, Arequipa, Peru, April 16\u201320, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7256, pp. 61\u201372. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-29344-3_6","DOI":"10.1007\/978-3-642-29344-3_6"},{"key":"840_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.01.027","journal-title":"Theor. Comput. Sci."},{"key":"840_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"HJ B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming, pp. 207\u2013218. Springer, Berlin, Heidelberg (2011)"},{"key":"840_CR8","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"key":"840_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"840_CR10","doi-asserted-by":"publisher","unstructured":"Chen, L., Hung, L., Lotze, H., Rossmanith, P.: Further results on online node- and edge-deletion problems with advice. In: L. Gasieniec, R. Klasing, T. Radzik (eds.) Combinatorial Algorithms\u201431st International Workshop, IWOCA 2020, Bordeaux, France, June 8\u201310, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12126, pp. 140\u2013153. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-48966-3_11","DOI":"10.1007\/978-3-030-48966-3_11"},{"issue":"1\u20133","key":"840_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theor. Comput. Sci. 332(1\u20133), 83\u2013108 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2004.08.015","journal-title":"Theor. Comput. Sci."},{"key":"840_CR12","unstructured":"Descartes, R.: Discours de la methode pour bien conduire sa raison, et chercher la verit\u00e9 dans les sciences. Plus la Dioptriqve. Les Meteores. Et la Geometrie\u2014Qui sont des essais de cete Methode. De l\u2019Imprimerie de Ian Maire (1637)"},{"issue":"3","key":"840_CR13","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. ITA 43(3), 585\u2013613 (2009). https:\/\/doi.org\/10.1051\/ita\/2009012","journal-title":"ITA"},{"issue":"24","key":"840_CR14","doi-asserted-by":"publisher","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.08.007","journal-title":"Theor. Comput. Sci."},{"key":"840_CR15","doi-asserted-by":"crossref","unstructured":"Greene, D.H., Knuth, D.E.: Mathematics for the Analysis of Algorithms, 3rd edn. Birkh\u00e4user (1990)","DOI":"10.1007\/978-0-8176-4729-2"},{"key":"840_CR16","unstructured":"Henrici, P.: Applied and Computational Complex Analysis, vol. 1. Wiley (1988)"},{"key":"840_CR17","doi-asserted-by":"publisher","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: P. Hlinen\u00fd, A. Kucera (eds.) Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23\u201327, 2010. Proceedings, Lecture Notes in Computer Science, vol. 6281, pp. 24\u201336. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_3","DOI":"10.1007\/978-3-642-15155-2_3"},{"key":"840_CR18","doi-asserted-by":"publisher","unstructured":"Komm, D.: An Introduction to Online Computation\u2014Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2","DOI":"10.1007\/978-3-319-42749-2"},{"key":"840_CR19","doi-asserted-by":"publisher","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., Kudahl, C.: Advice complexity of the online induced subgraph problem. In: P. Faliszewski, A. Muscholl, R. Niedermeier (eds.) 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22\u201326, 2016\u2014Krak\u00f3w, Poland, LIPIcs, vol.\u00a058, pp. 59:1\u201359:13. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.59","DOI":"10.4230\/LIPIcs.MFCS.2016.59"},{"key":"840_CR20","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10\u201315, pp. 3302\u20133311 (2018)"},{"key":"840_CR21","first-page":"9684","volume":"31","author":"M Purohit","year":"2018","unstructured":"Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. Adv. Neural Inf. Process. Syst. 31, 9684\u20139693 (2018)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"840_CR22","doi-asserted-by":"publisher","unstructured":"Rossmanith, P.: On the advice complexity of online edge- and node-deletion problems. In: Adventures Between Lower Bounds and Higher Altitudes\u2014Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday, pp. 449\u2013462 (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_26","DOI":"10.1007\/978-3-319-98355-4_26"},{"issue":"5","key":"840_CR23","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0002-9939-1962-0172273-0","volume":"13","author":"ES Wolk","year":"1962","unstructured":"Wolk, E.S.: The comparability graph of a tree. Proc. Am. Math. Soc. 13(5), 789\u2013795 (1962)","journal-title":"Proc. Am. Math. Soc."},{"key":"840_CR24","doi-asserted-by":"publisher","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: R.J. Lipton, W.A. Burkhard, W.J. Savitch, E.P. Friedman, A.V. Aho (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1\u20133, 1978, San Diego, California, USA, pp. 253\u2013264. ACM (1978). https:\/\/doi.org\/10.1145\/800133.804355","DOI":"10.1145\/800133.804355"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00840-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00840-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00840-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:05:52Z","timestamp":1628161552000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00840-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":24,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["840"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00840-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"4 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}