Parameterized approximability of maximizing the spread of influence in networks

DOI10.1016/j.jda.2014.05.001zbMath1361.68105OpenAlexW2119218916MaRDI QIDQ2250539

Morgan Chopin, Cristina Bazgan, Florian Sikora, André Nichterlein

Publication date: 7 July 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.05.001

zbMATH Keywords

approximationtarget set selectionviral marketingparameterized complexitydynamic monopoliesparameterized approximationspread of information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25)

Related Items (15)

Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ The complexity of finding effectors ⋮ Whom to befriend to influence people ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Evangelism in Social Networks ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Influence Diffusion in Social Networks under Time Window Constraints ⋮ On reconfigurability of target sets ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth governs the complexity of target set selection
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Spreading messages
• Some APX-completeness results for cubic graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Local majorities, coalitions and monopolies in graphs: A review
• Parametrized complexity theory.
• Detecting high log-densities
• On Tractable Cases of Target Set Selection
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The importance of being biased
• On the Approximability of Influence in Social Networks
• On Syntactic versus Computational Views of Approximability
• Exact and Approximation Algorithms for Densest k-Subgraph
• Constant Thresholds Can Make Target Set Selection Tractable
• Parameterized Inapproximability of Target Set Selection and Generalizations
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Variants of Spreading Messages
• Approximation Algorithms and Hardness for Domination with Propagation

This page was built for publication: Parameterized approximability of maximizing the spread of influence in networks