Further Results on Online Node- and Edge-Deletion Problems with Advice

Chen, Li-Hsuan; Hung, Ling-Ju; Lotze, Henri; Rossmanith, Peter

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 at all times. We consider graph classes that can be characterized by forbidden sets of induced subgraphs and analyze the advice complexity of getting an optimal solution. We give almost tight lower and upper bounds for the [Image: see text] , where there is one forbidden induced subgraph that may or may not be disconnected and tight bounds on the [Image: see text] , 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 [Formula: see text]. For the [Image: see text] the advice complexity is basically an easy function of the size of the biggest component in H.