DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.41

Forbidden Subgraph Problems with Predictions

Authors: Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm, and Moritz Stocker

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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.

Cite as

Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm, and Moritz Stocker. Forbidden Subgraph Problems with Predictions. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bockenhauer_et_al:LIPIcs.MFCS.2026.41,
  author =	{B\"{o}ckenhauer, Hans-Joachim and Jahn, Melvin and Komm, Dennis and Stocker, Moritz},
  title =	{{Forbidden Subgraph Problems with Predictions}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.41},
  URN =		{urn:nbn:de:0030-drops-274226},
  doi =		{10.4230/LIPIcs.MFCS.2026.41},
  annote =	{Keywords: online node deletion, competitive ratio, forbidden subgraphs, predictions}
}

Search Results

Documents authored by Jahn, Melvin

Forbidden Subgraph Problems with Predictions

Abstract

Cite as

Thanks for your feedback!

Could not send message