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

DOI10.1016/J.DISOPT.2019.05.004zbMATH Open1506.91132arXiv1805.10086OpenAlexW2962944345WikidataQ127728240 ScholiaQ127728240MaRDI QIDQ2010927FDOQ2010927

Authors: Stefan Ehard, Dieter Rautenbach 

Publication date: 28 November 2019

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Target set selection for conservative populations
• 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)