Abstract
We revisit two wellstudied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph G and a target degree Δ and we are asked either to edit or partition the graph so that the maximum degree becomes bounded by Δ. Both problems are known to be parameterized intractable for the most wellknown structural parameters, such as treewidth.
We revisit the parameterization by treewidth, as well as several related parameters and present a more finegrained picture of the complexity of both problems. In particular:
 Both problems admit straightforward DP algorithms with table sizes (Δ+2)^tw and (χ_d(Δ+1))^{tw} respectively, where tw is the input graph’s treewidth and χ_d the number of available colors. We show that, under the SETH, both algorithms are essentially optimal, for any nontrivial fixed values of Δ, χ_d, even if we replace treewidth by pathwidth. Along the way, we obtain an algorithm for Defective Coloring with complexity quasilinear in the table size, thus settling the complexity of both problems for treewidth and pathwidth.
 Given that the standard DP algorithm is optimal for treewidth and pathwidth, we then go on to consider the more restricted parameter treedepth. Here, previously known lower bounds imply that, under the ETH, Bounded Vertex Degree Deletion and Defective Coloring cannot be solved in time n^o(∜{td}) and n^o(√{td}) respectively, leaving some hope that a qualitatively faster algorithm than the one for treewidth may be possible. We close this gap by showing that neither problem can be solved in time n^o(td), under the ETH, by employing a recursive low treedepth construction that may be of independent interest.
 Finally, we consider a structural parameter that is known to be restrictive enough to render both problems FPT: vertex cover. For both problems the best known algorithm in this setting has a superexponential dependence of the form vc^?(vc). We show that this is optimal, as an algorithm with dependence of the form vc^o(vc) would violate the ETH. Our proof relies on a new application of the technique of ddetecting families introduced by Bonamy et al. [ToCT 2019].
Our results, although mostly negative in nature, paint a clear picture regarding the complexity of both problems in the landscape of parameterized complexity, since in all cases we provide essentially matching upper and lower bounds.
BibTeX  Entry
@InProceedings{lampis_et_al:LIPIcs.ESA.2023.77,
author = {Lampis, Michael and Vasilakis, Manolis},
title = {{Structural Parameterizations for Two Bounded Degree Problems Revisited}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {77:177: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/18730},
URN = {urn:nbn:de:0030drops187302},
doi = {10.4230/LIPIcs.ESA.2023.77},
annote = {Keywords: ETH, Parameterized Complexity, SETH}
}
Keywords: 

ETH, Parameterized Complexity, SETH 
Collection: 

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

2023 
Date of publication: 

30.08.2023 