You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Online Node- and Edge-Deletion Problems with Advice
Contributor:
Chen, Li-Hsuan;
Hung, Ling-Ju;
Lotze, Henri;
Rossmanith, Peter
Published:
Springer Science and Business Media LLC, 2021
Published in:
Algorithmica, 83 (2021) 9, Seite 2719-2753
Language:
English
DOI:
10.1007/s00453-021-00840-9
ISSN:
0178-4617;
1432-0541
Origination:
Footnote:
Description:
AbstractIn 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.