Abstract
The notion of ℋtreewidth, where ℋ is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly speaking, a graph of ℋtreewidth at most k can be decomposed into (arbitrarily large) ℋsubgraphs which interact only through vertex sets of size 𝒪(k) which can be organized in a treelike fashion. ℋtreewidth can be used as a hybrid parameterization to develop fixedparameter tractable algorithms for ℋdeletion problems, which ask to find a minimum vertex set whose removal from a given graph G turns it into a member of ℋ. The bottleneck in the current parameterized algorithms lies in the computation of suitable tree ℋdecompositions.
We present FPTapproximation algorithms to compute tree ℋdecompositions for hereditary and unionclosed graph classes ℋ. Given a graph of ℋtreewidth k, we can compute a 5approximate tree ℋdecomposition in time f(𝒪(k)) ⋅ n^𝒪(1) whenever ℋdeletion parameterized by solution size can be solved in time f(k) ⋅ n^𝒪(1) for some function f(k) ≥ 2^k. The currentbest algorithms either achieve an approximation factor of k^𝒪(1) or construct optimal decompositions while suffering from nonuniformity with unknown parameter dependence. Using these decompositions, we obtain algorithms solving Odd Cycle Transversal in time 2^𝒪(k) ⋅ n^𝒪(1) parameterized by bipartitetreewidth and Vertex Planarization in time 2^𝒪(k log k) ⋅ n^𝒪(1) parameterized by planartreewidth, showing that these can be as fast as the solutionsize parameterizations and giving the first ETHtight algorithms for parameterizations by hybrid width measures.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs.ESA.2023.66,
author = {Jansen, Bart M. P. and de Kroon, Jari J. H. and W{\l}odarczyk, Micha{\l}},
title = {{5Approximation for ℋTreewidth Essentially as Fast as ℋDeletion Parameterized by Solution Size}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {66:166:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18719},
URN = {urn:nbn:de:0030drops187195},
doi = {10.4230/LIPIcs.ESA.2023.66},
annote = {Keywords: fixedparameter tractability, treewidth, graph decompositions}
}
Keywords: 

fixedparameter tractability, treewidth, graph decompositions 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 