Some results on the target set selection problem

DOI10.1007/S10878-012-9518-3MaRDI QIDQ1956258zbMATH OpenOpenAlexFDO

Authors Chun-Ying Chiang, Liang-Hao Huang, Bo-Jr Li, Jiaojiao Wu, Hong-Gwa Yeh

Publication date 13 June 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

block graphblock-cactus graphchordal graphdiffusion of innovationsdynamic monopolyHamming graphirreversible spread of influencesocial networkstarget set selectiontreeviral marketing

Mathematics Subject Classification ID

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

Abstract: In this paper we consider a fundamental problem in the area of viral marketing, called T{scriptsize ARGET} S{scriptsize ET} S{scriptsize ELECTION} problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if $G$ is a block-cactus graph, then the T{scriptsize ARGET} S{scriptsize ET} S{scriptsize ELECTION} problem can be solved in linear time, which generalizes Chen's result cite{chen2009} for trees, and the time complexity is much better than the algorithm in cite{treewidth} (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph $G$ is a chordal graph with thresholds $heta(v)leq2$ for each vertex $v$ in $G$, then the problem can be solved in linear time. For a Hamming graph $G$ having thresholds $heta(v)=2$ for each vertex $v$ of $G$, we precisely determine an optimal target set $S$ for $(G,heta)$. These results partially answer an open problem raised by Dreyer and Roberts cite{Dreyer2009}.

Recommendations

• On tractable cases of target set selection
• On approximating target set selection
• Combinatorial model and bounds for target set selection
• Domination and convexity problems in the target set selection model
• Target set selection parameterized by vertex cover and more
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• A global optimization algorithm for target set selection problems
• Parameterized inapproximability of target set selection and generalizations
• Parameterized inapproximability of target set selection and generalizations

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Dynamic monopolies in tori.
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• Incidence matrices and interval graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Local majorities, coalitions and monopolies in graphs: A review
• On rigid circuit graphs
• On the approximability of influence in social networks
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Treewidth governs the complexity of target set selection

Cited in

(42)

• Computational approaches for zero forcing and related problems
• Discovering small target sets in social networks: a fast and effective algorithm
• Dynamic monopolies for interval graphs with bounded thresholds
• 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
• Target set selection parameterized by vertex cover and more
• On reconfigurability of target sets
• On the harmless set problem parameterized by treewidth
• Target set selection on generalized pancake graphs
• Constant thresholds can make target set selection tractable
• Fast and frugal targeting with incentives
• Partial immunization of trees
• The complexity of finding harmless individuals in social networks
• 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
• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• A global optimization algorithm for target set selection problems
• Vaccinate your trees!
• Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems
• Evangelism in social networks
• Influence Diffusion in Social Networks under Time Window Constraints
• On dynamic monopolies of graphs with probabilistic thresholds
• Diffusion centrality: a paradigm to maximize spread in social networks
• Target set selection in Cartesian product graphs.
• Optimizing spread of influence in social networks via partial incentives
• A fast and effective heuristic for discovering small target sets in social networks
• Combinatorial model and bounds for target set selection
• Target Set Selection in Dense Graph Classes
• Improved Computational Approaches and Heuristics for Zero Forcing
• Target set selection problem for honeycomb networks
• Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
• Establishing herd immunity is hard even in simple geometric networks
• Weighted target set selection on trees and cycles
• Target set selection with maximum activation time
• On Structural Parameterizations of the Harmless Set Problem
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• On the complexity of target set selection in simple geometric networks
• Parameterized complexity of weighted target set selection
• Minimal zero forcing sets
• Parameterized complexity of weighted target set selection
• Bounds on the k-conversion number

This page was built for publication: Some results on the target set selection problem

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