Distance Vector Domination
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- A simple optimal algorithm for k-tuple dominating problem in interval graphsJournal of Combinatorial Optimization, 2022
- Distance Domination in Graphs2020
- A survey on influence maximization in a social networkKnowledge and Information Systems, 2020
- Discovering Small Target Sets in Social Networks: A Fast and Effective AlgorithmAlgorithmica, 2017
- Evangelism in social networks: Algorithms and complexityNetworks, 2017
- Algorithmic Meta-theorems for Restrictions of TreewidthAlgorithmica, 2011
- Restricted domination parameters in graphsJournal of Combinatorial Optimization, 2006
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- An analysis of the greedy algorithm for the submodular set covering problemCombinatorica, 1982
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967