Distance Vector Domination
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917875494682624 |
|---|---|
| author | Cordasco, Gennaro Garagano, Luisa Rescigno, Adele A. |
| author_facet | Cordasco, Gennaro Garagano, Luisa Rescigno, Adele A. |
| contents | Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named {\em Distance Vector Domination} generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are $1$. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15663 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distance Vector Domination Cordasco, Gennaro Garagano, Luisa Rescigno, Adele A. Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named {\em Distance Vector Domination} generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are $1$. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations. |
| title | Distance Vector Domination |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2412.15663 |