Distance Vector Domination
| Autor: | Cordasco, Gennaro, Garagano, Luisa, Rescigno, Adele A. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: This paper will appear in the proceedings of SOFSEM 2025 |
| Databáze: | arXiv |
| Externí odkaz: |
|