Parameterized complexity of modular dominating structures in bounded-treewidth graphs
Utilitas Mathematica · 31.03.2026 · 126 · 235-266
DOI: 10.61091/um126-12 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 31.03.2026. Verfasst von Dhilshath Shajahan.
Abstract (Originalsprache)
We study a modular generalization of the (σ, ρ)-Dominating Set problem on graphs of bounded treewidth, where vertices must satisfy neighborhood constraints modulo a fixed integer m. We present a dynamic programming algorithm over tree decompositions that achieves a runtime of O(n ⋅ (2m)2tw + 2) and space usage O(n ⋅ (2m)tw + 1), establishing fixed-parameter tractability when both treewidth tw and log m are treated as parameters. We prove this bound exhibits the correct exponential dependence on twlog m, as this factor is inherent to modular constraint satisfaction under the Strong Exponential Time Hypothesis (SETH). Experimental evaluation on synthetic graphs confirms the algorithm’s efficiency for small values of tw and m, highlighting its applicability to network design, logic circuits, and distributed systems with modular constraints.
Zitieren
APA
Shajahan, D. (2026). Parameterized complexity of modular dominating structures in bounded-treewidth graphs. Utilitas Mathematica, 126, 235-266. https://doi.org/10.61091/um126-12
Vancouver
Shajahan D. Parameterized complexity of modular dominating structures in bounded-treewidth graphs. Utilitas Mathematica. 2026;126:235-266. doi:10.61091/um126-12
BibTeX
@article{Shajahan2026,
author = {Shajahan, Dhilshath},
title = {Parameterized complexity of modular dominating structures in bounded-treewidth graphs},
journal = {Utilitas Mathematica},
year = {2026},
volume = {126},
pages = {235--266},
doi = {10.61091/um126-12}
}
EUVIMED