On some tractable and hard instances for partial incentives and target set selection

DOI10.1016/J.DISOPT.2019.05.004MaRDI QIDQ2010927zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Ehard, Dieter Rautenbach

Publication date 28 November 2019

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.10086

zbMATH Keywords

planar graphtarget setchordal graphdynamic monopolydegenerate setpartial incentive

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Approximation algorithms (68W25) Microeconomic theory (price theory and economic markets) (91B24)

Abstract: A widely studied model for influence diffusion in social networks are {it target sets}. For a graph $G$ and an integer-valued threshold function $au$ on its vertex set, a {it target set} or {it dynamic monopoly} is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $au(u)$ neighbors in it eventually yields the entire vertex set of $G$. This notion is limited to the binary choice of including a vertex in the target set or not, and Cordasco et al.~proposed {it partial incentives} as a variant allowing for intermediate choices. We show that finding optimal partial incentives is hard for chordal graphs and planar graphs but tractable for graphs of bounded treewidth and for interval graphs with bounded thresholds. We also contribute some new results about target set seletion on planar graphs by showing the hardness of this problem, and by describing an efficient $O(sqrtn)$-approximation algorithm as well as a PTAS for the dual problem of finding a maximum degenerate set.

Recommendations

• Fast and frugal targeting with incentives
• Constant thresholds can make target set selection tractable
• Treewidth governs the complexity of target set selection
• Constant thresholds can make target set selection tractable
• On tractable cases of target set selection

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A partial k-arboretum of graphs with bounded treewidth
• Approximation Algorithms and Hardness for Domination with Propagation
• Approximation algorithms for NP-complete problems on planar graphs
• Bidimensionality: new connections between FPT algorithms and PTASs
• Combinatorial model and bounds for target set selection
• Complexity of Finding Embeddings in a k-Tree
• Constant thresholds can make target set selection tractable
• Dynamic monopolies for interval graphs with bounded thresholds
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Irreversible 2-conversion set in graphs of bounded degree
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• New bounds for contagious sets
• On the approximability of influence in social networks
• Optimization, approximation, and complexity classes
• Optimizing spread of influence in social networks via partial incentives
• Some results on the target set selection problem
• Some simplified NP-complete graph problems
• Target set selection parameterized by clique-width and maximum threshold
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth governs the complexity of target set selection
• Treewidth of graphs with balanced separations
• Treewidth. Computations and approximations

Cited in

(6)

• Target set selection for conservative populations
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
• Fast and frugal targeting with incentives
• Target set selection with maximum activation time
• Domination and convexity problems in the target set selection model

This page was built for publication: On some tractable and hard instances for partial incentives and target set selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010927)