Treewidth governs the complexity of target set selection

DOI10.1016/j.disopt.2010.09.007zbMath1248.90068OpenAlexW2148732839MaRDI 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 networkstarget set selectionviral marketinggame of lifebounded tree-width algorithmbounded tree-width lower-bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

A parameterized complexity view on collapsing \(k\)-cores ⋮ Computational approaches for zero forcing and related problems ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ Vaccinate your trees! ⋮ Target Set Selection in Dense Graph Classes ⋮ Optimizing Spread of Influence in Social Networks via Partial Incentives ⋮ On the harmless set problem parameterized by treewidth ⋮ Parameterized complexity of immunization in the threshold model ⋮ Least cost influence propagation in (social) networks ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Weighted target set selection on trees and cycles ⋮ 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\) ⋮ Unnamed Item ⋮ Domination and convexity problems in the target set selection model ⋮ Some results on the target set selection problem ⋮ Latency-bounded target set selection in social networks ⋮ Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks ⋮ Active influence spreading in social networks ⋮ Target set selection for conservative populations ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ The complexity of finding effectors ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ Constant thresholds can make target set selection tractable ⋮ 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 ⋮ How to choose friends strategically ⋮ Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis ⋮ Whom to befriend to influence people ⋮ Partial immunization of trees ⋮ Evangelism in Social Networks ⋮ Target set selection parameterized by vertex cover and more ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ 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 ⋮ Influence Diffusion in Social Networks under Time Window Constraints ⋮ On irreversible spread of influence in edge-weighted graphs ⋮ On reconfigurability of target sets ⋮ Exact solutions for latency-bounded target set selection problem on some special families of graphs

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

This page was built for publication: Treewidth governs the complexity of target set selection