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 (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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parameterized Complexity of (d, r)-Domination via Modular Decomposition

  • Gennaro Cordasco,
  • Luisa Gargano,
  • Adele A. Rescigno

摘要

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 (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.