Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2506.14564 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908685687586816 |
|---|---|
| author | Geis, Lukas Leonhardt, Alexander Meintrup, Johannes Meyer, Ulrich Penschuck, Manuel Retschmeier, Lukas |
| author_facet | Geis, Lukas Leonhardt, Alexander Meintrup, Johannes Meyer, Ulrich Penschuck, Manuel Retschmeier, Lukas |
| contents | Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D \subseteq V$ of minimal cardinality such that every vertex either is in $D$ or adjacent to a member of $D$. Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of DominatingSet, data reduction rules are extensively used in practice. In this context, Rule1 due to Alber, Fellows, and Niedermeier [JACM 2004] has been shown to be very powerful, yet its best-known running time is $\mathcal{O}(n^3)$ ($= \mathcal{O}(nm)$) for general graphs. In this work, we propose, to the best of our knowledge, the first $\mathcal{O}(n + m)$-time algorithm for Rule1 on general graphs. We additionally propose simple, but practically significant, extensions to our algorithmic framework to further prune the input instances. We complement our theoretical claims with experiments that confirm the practicality of our approach. On average, we see significant speedups of over one order of magnitude while removing $59.8\times$ more nodes and $410.9\times$ more edges than the original formulation across a large dataset comprised of real-world and synthetic networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14564 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting a Successful Reduction Rule for Dominating Set Geis, Lukas Leonhardt, Alexander Meintrup, Johannes Meyer, Ulrich Penschuck, Manuel Retschmeier, Lukas Data Structures and Algorithms Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D \subseteq V$ of minimal cardinality such that every vertex either is in $D$ or adjacent to a member of $D$. Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of DominatingSet, data reduction rules are extensively used in practice. In this context, Rule1 due to Alber, Fellows, and Niedermeier [JACM 2004] has been shown to be very powerful, yet its best-known running time is $\mathcal{O}(n^3)$ ($= \mathcal{O}(nm)$) for general graphs. In this work, we propose, to the best of our knowledge, the first $\mathcal{O}(n + m)$-time algorithm for Rule1 on general graphs. We additionally propose simple, but practically significant, extensions to our algorithmic framework to further prune the input instances. We complement our theoretical claims with experiments that confirm the practicality of our approach. On average, we see significant speedups of over one order of magnitude while removing $59.8\times$ more nodes and $410.9\times$ more edges than the original formulation across a large dataset comprised of real-world and synthetic networks. |
| title | Revisiting a Successful Reduction Rule for Dominating Set |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.14564 |