Parameterized Complexity of (d,r)-Domination via Modular Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913737372336128 |
|---|---|
| author | Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. |
| author_facet | Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. |
| contents | With the rise of social media, misinformation has significant negative effects on the decision-making of individuals, organizations and communities within society. Identifying and mitigating the spread of fake information is a challenging issue. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, through an awareness process, can prevent the spreading of fake narratives. The considered problem, named \textsc{$(d,r)$-Domination} generalizes both distance and multiple domination. We study the parameterized complexity of the problem according to standard and structural parameters. We give fixed-parameter algorithms as well as polynomial compressions/kernelizations for some variants of the problem and parameter combinations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15671 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of (d,r)-Domination via Modular Decomposition Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics With the rise of social media, misinformation has significant negative effects on the decision-making of individuals, organizations and communities within society. Identifying and mitigating the spread of fake information is a challenging issue. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, through an awareness process, can prevent the spreading of fake narratives. The considered problem, named \textsc{$(d,r)$-Domination} generalizes both distance and multiple domination. We study the parameterized complexity of the problem according to standard and structural parameters. We give fixed-parameter algorithms as well as polynomial compressions/kernelizations for some variants of the problem and parameter combinations. |
| title | Parameterized Complexity of (d,r)-Domination via Modular Decomposition |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2412.15671 |