A Linear Kernel for Planar Total Dominating Set
A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when parameterized by the solution size. By the meta...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3295/pdf |
| _version_ | 1827323755410489344 |
|---|---|
| author | Valentin Garnero Ignasi Sau |
| author_facet | Valentin Garnero Ignasi Sau |
| author_sort | Valentin Garnero |
| collection | DOAJ |
| description | A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such
that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total
dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on
general graphs when parameterized by the solution size. By the meta-theorem of
Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total
Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how
such a kernel can be effectively constructed, and how to obtain explicit
reduction rules with reasonably small constants. Following the approach of
Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating
Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the
solution. This result complements several known constructive linear kernels on
planar graphs for other domination problems such as Dominating Set, Edge
Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue
Dominating Set. |
| first_indexed | 2024-04-25T01:58:42Z |
| format | Article |
| id | doaj.art-9128c70ec4a54bfa8871221cbee9949f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:42Z |
| publishDate | 2018-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-9128c70ec4a54bfa8871221cbee9949f2024-03-07T15:36:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-05-01Vol. 20 no. 1Discrete Algorithms10.23638/DMTCS-20-1-143295A Linear Kernel for Planar Total Dominating SetValentin GarneroIgnasi SauA total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when parameterized by the solution size. By the meta-theorem of Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how such a kernel can be effectively constructed, and how to obtain explicit reduction rules with reasonably small constants. Following the approach of Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the solution. This result complements several known constructive linear kernels on planar graphs for other domination problems such as Dominating Set, Edge Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue Dominating Set.https://dmtcs.episciences.org/3295/pdfcomputer science - data structures and algorithms05c85, 05c10g.2.2 |
| spellingShingle | Valentin Garnero Ignasi Sau A Linear Kernel for Planar Total Dominating Set Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms 05c85, 05c10 g.2.2 |
| title | A Linear Kernel for Planar Total Dominating Set |
| title_full | A Linear Kernel for Planar Total Dominating Set |
| title_fullStr | A Linear Kernel for Planar Total Dominating Set |
| title_full_unstemmed | A Linear Kernel for Planar Total Dominating Set |
| title_short | A Linear Kernel for Planar Total Dominating Set |
| title_sort | linear kernel for planar total dominating set |
| topic | computer science - data structures and algorithms 05c85, 05c10 g.2.2 |
| url | https://dmtcs.episciences.org/3295/pdf |
| work_keys_str_mv | AT valentingarnero alinearkernelforplanartotaldominatingset AT ignasisau alinearkernelforplanartotaldominatingset AT valentingarnero linearkernelforplanartotaldominatingset AT ignasisau linearkernelforplanartotaldominatingset |