Online Node- and Edge-Deletion Problems with Advice

Algorithmica, vol. 83, pp. 2719–2753

Abstract

Abstract 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 $$ Π at all times. We consider only hereditary properties $$\Pi $$ Π , for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs $${{\mathcal{F}}}$$ F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed Connected $${{\mathcal{F}}}$$ F -Node-Deletion Problem, where all graphs of the family $${\mathcal{F}}$$ F have to be connected and almost tight lower and upper bounds for the Delayed $$H$$ H -Node-Deletion Problem, where there is one forbidden induced subgraph H that may be connected or not. For the Delayed $$H$$ H -Node-Deletion Problem the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected $${\mathcal{F}}$$ F -Edge-Deletion Problem, 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 $${\mathcal{F}}$$ F . We give a separate analysis for the Delayed Connected $$H$$ H -Edge-Deletion Problem, which is less general but admits a bound that is easier to compute.

Authors 4

1. Li-Hsuan Chen
   Affiliation as printed

   Pro Brand International (TW), Inc., Hsinchu, Taiwan

2. Ling-Ju Hung

   National Taipei University of Business

   Affiliation as printed

   National Taipei University of Business, Taipei, Taiwan

3. Henri Lotze corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

4. Peter Rossmanith Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany