Faster FPT Algorithms for Deletion to Pairs of Graph Classes

Autor:	Venkatesh Raman, Diptapriyo Majumdar, Ashwin Jacob
Rok vydání:	2021
Předmět:	Combinatorics Vertex deletion Class (set theory) Integer Vertex cover Iterative compression Graph (abstract data type) Parameterized complexity Feedback vertex set MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Fundamentals of Computation Theory ISBN: 9783030865924 FCT
DOI:	10.1007/978-3-030-86593-1_22
Popis:	Let \(\varPi \) be a hereditary graph class. The problem of deletion to \(\varPi \), takes as input a graph G and asks for a minimum number (or a fixed integer k) of vertices to be deleted from G so that the resulting graph belongs to \(\varPi \). This is a well-studied problem in paradigms including approximation and parameterized complexity. This problem, for example, generalizes vertex cover, feedback vertex set, cluster vertex deletion, perfect deletion to name a few. The study of this problem in parameterized complexity has resulted in several powerful algorithmic techniques including iterative compression and important separators.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::87235d23e022deeca4b22904f894c521 https://doi.org/10.1007/978-3-030-86593-1_22 Zobrazit plný text záznamu