Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

The parameterised complexity of generalised temporal domination on temporal graphs with modular structure

  • Jessica Enright
  • Kitty Meeks
  • Elena Moss
Open at sourcePDFDOICite

Abstract

Inspired by the static problem (α,β)-Dominating Set, we propose a general temporal domination problem, called (α,β)-Temporal Dominating Set ((α,β)-TDS). We show that this problem encompasses Temporal Dominating Set, and additionally provides first temporal extensions of problems such as k-Dominating Set and α-Dominating Set. In this paper, we study the parameterised complexity of (α,β)-TDS with respect to temporal neighbourhood diversity (TND), temporal modular-width (TMW), and temporal cliquewidth (TCW). We obtain fixed parameter tractability results for all values of α and β with respect to TND; W[1]-hardness with respect to TMW and TCW whenever β is in the problem input, or whenever α∈ (0,1) and β is a fixed constant; and para-NP-hardness with respect to TCW when α= 0 and β= 1, or α= 1 and β= 0.

Related

  1. On k-limited domination: complexity and Cartesian products
    Aleksandra Tepeh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On k-limited domination: complexity and Sierpiński graphs
    Dragana Božović
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
    Julian D. Allagan, Kevin Pereyra, William A. Massey
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  4. Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
    Florent Foucaud, Yan Gerard, Christian Laforest +1
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  5. Temporal and climatic drivers of uncomplicated malaria in Ghana: Regional Generalised Additive and Generalised Additive Mixed Model analysis
    Edward Akurugu, Timothy Awine, Baba Seidu +5
    PLOS OnePeer-reviewedCC BY 4.0Full text1 citedAtmospheric science & meteorologyClimate sciencePLOSPMC

Cite

BibTeXRIS
BibTeX
@misc{enright2026parameterised,
  title = {{The parameterised complexity of generalised temporal domination on temporal graphs with modular structure}},
  author = {Jessica Enright and Kitty Meeks and Elena Moss},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26366},
  eprint = {2609.26366},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26366},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
AU  - Jessica Enright
AU  - Kitty Meeks
AU  - Elena Moss
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26366
UR  - https://arxiv.org/abs/2609.26366
AB  - Inspired by the static problem (α,β)-Dominating Set, we propose a general temporal domination problem, called (α,β)-Temporal Dominating Set ((α,β)-TDS). We show that this problem encompasses Temporal Dominating Set, and additionally provides first temporal extensions of problems such as k-Dominating Set and α-Dominating Set. In this paper, we study the parameterised complexity of (α,β)-TDS with respect to temporal neighbourhood diversity (TND), temporal modular-width (TMW), and temporal cliquewidth (TCW). We obtain fixed parameter tractability results for all values of α and β with respect to TND; W[1]-hardness with respect to TMW and TCW whenever β is in the problem input, or whenever α∈ (0,1) and β is a fixed constant; and para-NP-hardness with respect to TCW when α= 0 and β= 1, or α= 1 and β= 0.
ER  -