EUVIMEDEUVIMED entdecken
Crossref

Parameterized complexity of modular dominating structures in bounded-treewidth graphs

Dhilshath Shajahan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →