Constant thresholds can make target set selection tractable
From MaRDI portal
Publication:2254488
DOI10.1007/s00224-013-9499-3zbMath1319.68109OpenAlexW3022472023MaRDI QIDQ2254488
André Nichterlein, Morgan Chopin, Mathias Weller, Rolf Niedermeier
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9499-3
Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
A parameterized complexity view on collapsing \(k\)-cores, Hardness Results for Seeding Complex Contagion with Neighborhoods, Discovering small target sets in social networks: a fast and effective algorithm, Target Set Selection in Dense Graph Classes, On the harmless set problem parameterized by treewidth, Establishing herd immunity is hard even in simple geometric networks, Groups burning: analyzing spreading processes in community-based networks, Target set selection with maximum activation time, Solving target set selection with bounded thresholds faster than \(2^n\), Target set selection on generalized pancake graphs, Domination and convexity problems in the target set selection model, Active influence spreading in social networks, Dynamic monopolies for interval graphs with bounded thresholds, Solving Target Set Selection with Bounded Thresholds Faster than 2^n, Approximate association via dissociation, The complexity of finding effectors, On some tractable and hard instances for partial incentives and target set selection, The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs, Unnamed Item, Whom to befriend to influence people, Evangelism in Social Networks, Target set selection parameterized by vertex cover and more, The complexity of finding harmless individuals in social networks, On reconfigurability of target sets, On the complexity of the vector connectivity problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial model and bounds for target set selection
- New bounds for contagious sets
- Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
- Treewidth governs the complexity of target set selection
- Irreversible conversion of graphs
- Fixed-parameter algorithms for cluster vertex deletion
- On the parameterized complexity of multiple-interval graph problems
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Spreading messages
- Local majorities, coalitions and monopolies in graphs: A review
- Some results on the target set selection problem
- Dynamic monopolies and feedback vertex sets in hexagonal grids
- Parametrized complexity theory.
- New Races in Parameterized Algorithmics
- Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Integer Programming with a Fixed Number of Variables
- On the Approximability of Influence in Social Networks
- Kernelization: New Upper and Lower Bound Techniques
- Bootstrap Percolation in High Dimensions
- Parameterized Approximability of Maximizing the Spread of Influence in Networks
- On Dominating Sets and Independent Sets of Graphs
- Reducibility among Combinatorial Problems
- Parameterized and Exact Computation
- Parameterized Algorithms for Generalized Domination
- Variants of Spreading Messages
