Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.17485 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911016526282752 |
|---|---|
| author | Retschmeier, Lukas |
| author_facet | Retschmeier, Lukas |
| contents | For a given graph $G = (V, E)$, a subset of the vertices $D\subseteq V$ is called a semitotal dominating set, if $D$ is a dominating set and every vertex $v \in D$ is within distance two to another witness $v' \in D$. We want to find a semitotal dominating set of minimum cardinality. We show that the problem is $\mathrm{W}[2]$-hard on bipartite and split graphs when parameterized by the solution size $k$. On the positive side, we extend the kernelization technique of Alber, Fellows, and Niedermeier [JACM 2004] to obtain a linear kernel of size $358k$ on planar graphs. This result complements known linear kernels already known for several variants, including Total, Connected, Red-Blue, Efficient, Edge, and Independent Dominating Set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17485 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Parameterized Complexity of Semitotal Domination on Graph Classes Retschmeier, Lukas Computational Complexity For a given graph $G = (V, E)$, a subset of the vertices $D\subseteq V$ is called a semitotal dominating set, if $D$ is a dominating set and every vertex $v \in D$ is within distance two to another witness $v' \in D$. We want to find a semitotal dominating set of minimum cardinality. We show that the problem is $\mathrm{W}[2]$-hard on bipartite and split graphs when parameterized by the solution size $k$. On the positive side, we extend the kernelization technique of Alber, Fellows, and Niedermeier [JACM 2004] to obtain a linear kernel of size $358k$ on planar graphs. This result complements known linear kernels already known for several variants, including Total, Connected, Red-Blue, Efficient, Edge, and Independent Dominating Set. |
| title | On the Parameterized Complexity of Semitotal Domination on Graph Classes |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.17485 |