Abstract
For a graph class 𝒢, we define the 𝒢modular cardinality of a graph G as the minimum size of a vertex partition of G into modules that each induces a graph in 𝒢. This generalizes other modulebased graph parameters such as neighborhood diversity and iterated type partition. Moreover, if 𝒢 has bounded modularwidth, the W[1]hardness of a problem in 𝒢modular cardinality implies hardness on modularwidth, cliquewidth, and other related parameters. Several FPT algorithms based on modular partitions compute a solution table in each module, then combine each table into a global solution. This works well when each table has a succinct representation, but as we argue, when no such representation exists, the problem is typically W[1]hard. We illustrate these ideas on the generic (α, β)domination problem, which is a generalization of known domination problems such as Bounded Degree Deletion, kDomination, and αDomination. We show that for graph classes 𝒢 that require arbitrarily large solution tables, these problems are W[1]hard in the 𝒢modular cardinality, whereas they are fixedparameter tractable when they admit succinct solution tables. This leads to several new positive and negative results for many domination problems parameterized by known and novel structural graph parameters such as cliquewidth, modularwidth, and clustermodular cardinality.
BibTeX  Entry
@InProceedings{lafond_et_al:LIPIcs.MFCS.2023.61,
author = {Lafond, Manuel and Luo, Weidong},
title = {{Parameterized Complexity of Domination Problems Using Restricted Modular Partitions}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {61:161:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18595},
URN = {urn:nbn:de:0030drops185958},
doi = {10.4230/LIPIcs.MFCS.2023.61},
annote = {Keywords: modularwidth, parameterized algorithms, Whardness, 𝒢modular cardinality}
}
Keywords: 

modularwidth, parameterized algorithms, Whardness, 𝒢modular cardinality 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 