2018/05/25 by Stefan Ehard, Dieter Rautenbach, Ehard, Stefan +1
Economics, Econometrics and Finance · Physics and Astronomy · Social Sciences · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Electoral Systems and Political Participation #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Opinion Dynamics and Social Influence
paper · pdf · doi:10.48550/arxiv.1805.10086
openalex publication_date 2018/05/25 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
A widely studied model for influence diffusion in social networks are it\ntarget sets. For a graph G and an integer-valued threshold function \τ\non its vertex set, a it target set or it dynamic monopoly is a set of\nvertices of G such that iteratively adding to it vertices u of G that\nhave at least \τ(u) neighbors in it eventually yields the entire vertex set\nof G. This notion is limited to the binary choice of including a vertex in\nthe target set or not, and Cordasco et al.~proposed it partial incentives as\na variant allowing for intermediate choices.\n We show that finding optimal partial incentives is hard for chordal graphs\nand planar graphs but tractable for graphs of bounded treewidth and for\ninterval graphs with bounded thresholds. We also contribute some new results\nabout target set seletion on planar graphs by showing the hardness of this\nproblem, and by describing an efficient O(\√(n))-approximation algorithm\nas well as a PTAS for the dual problem of finding a maximum degenerate set.\n