2013/03/31 by Cristina Bazgan, Morgan Chopin, André Nichterlein +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Approximation algorithm #Binary logarithm #Bounded function #Combinatorics #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #Degree (music) #Discrete mathematics #Graph #Mathematics #Parameterized complexity #Physics #Time complexity #Vertex (graph theory) #cs.DS #cs.SI
paper · pdf · doi:10.1016/j.jda.2014.05.001
published as Journal of Discrete Algorithms (27), 2014, 54--65
openalex publication_date 2014/06/02 · arxiv created 2014/08/17 · arxiv updated 2014/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value~thr(v) attached to each vertex~v, the spread of influence is modeled as follows: A vertex~v becomes "active" (influenced) if at least thr(v) of its neighbors are active. In the corresponding optimization problem the objective is then to find a fixed number of vertices to activate such that the number of activated vertices at the end of the propagation process is maximum. We show that this problem is strongly inapproximable in fpt-time with respect to (w.r.t.) parameter k even for very restrictive thresholds. In the case that the threshold of each vertex equals its degree, we prove that the problem is inapproximable in polynomial time and it becomes r(n)-approximable in fpt-time w.r.t. parameter k for any strictly increasing function r. Moreover, we show that the decision version is W[1]-hard w.r.t. parameter k but becomes fixed-parameter tractable on bounded degree graphs.