2026-08-21T18:34:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27422 2026-08-21T14:42:39Z ddc:004 open_access

Forbidden Subgraph Problems with Predictions Böckenhauer, Hans-Joachim Jahn, Melvin Komm, Dennis Stocker, Moritz online node deletion competitive ratio forbidden subgraphs predictions In the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected induced forbidden subgraph H at each point in time. To achieve this, an algorithm must, upon each occurrence of H, identify and irrevocably delete one or more vertices. The objective is to delete as few vertices as possible. We provide tight bounds on the competitive ratio for forbidden subgraphs H that do not contain true twins or that do not contain false twins. We further consider the problem within the model of predictions, where the algorithm is provided with a single bit of advice for each revealed vertex. These predictions are considered to be provided by an untrusted source and may be incorrect. We present a family of algorithms solving the problem with predictions and show that it is Pareto-optimal with respect to consistency and robustness for the online vertex cover problem, for 2-connected forbidden subgraphs that do not contain true twins or that do not contain false twins, as well as for any forbidden path of length at least five. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans-Joachim Böckenhauer and Melvin Jahn and Dennis Komm and Moritz Stocker 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.41 urn:nbn:de:0030-drops-274226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.41 eng https://creativecommons.org/licenses/by/4.0/legalcode