Treewidth governs the complexity of target set selection

DOI10.1016/j.disopt.2010.09.007zbMath1248.90068MaRDI QIDQ456700

Danny Hermelin, Oren Ben-Zwi, Daniel Lokshtanov, Ilan Newman

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.007

zbMATH Keywords

social networks; target set selection; viral marketing; game of life; bounded tree-width algorithm; bounded tree-width lower-bound

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

Structure of Graphs with Locally Restricted Crossings, How to choose friends strategically, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, Exact solutions for latency-bounded target set selection problem on some special families of graphs, The complexity of finding effectors, On the complexity of reasoning about opinion diffusion under majority dynamics, Computational approaches for zero forcing and related problems, Discovering small target sets in social networks: a fast and effective algorithm, Least cost influence propagation in (social) networks, Active influence spreading in social networks, Dynamic monopolies for interval graphs with bounded thresholds, Some results on the target set selection problem, On some tractable and hard instances for partial incentives and target set selection, Parameterized approximability of maximizing the spread of influence in networks, Constant thresholds can make target set selection tractable, Whom to befriend to influence people, Partial immunization of trees, The complexity of finding harmless individuals in social networks, Parameterizations of hitting set of bundles and inverse scope, Influence diffusion in social networks under time window constraints, Spread of influence in weighted networks under time and budget constraints, Latency-bounded target set selection in social networks, Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks, Vaccinate your trees!, Evangelism in Social Networks, Influence Diffusion in Social Networks under Time Window Constraints, On irreversible spread of influence in edge-weighted graphs, Optimizing Spread of Influence in Social Networks via Partial Incentives, A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• Size bounds for dynamic monopolies
• On treewidth approximations.
• Local majorities, coalitions and monopolies in graphs: A review
• Dynamic monopolies of constant size
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Relationships between nondeterministic and deterministic tape complexities
• Tight lower bounds for certain parameterized NP-hard problems
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Contagion
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Automata, Languages and Programming