TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 02.05.2013


Page Content

to Navigation

Parameterized Approximability of Maximizing the Spread of Influence in Networks

Dipl.-Inf. André Nichterlein (TU Berlin)

We consider the problem of maximizing the spread of influence through a social network. Here, we are given a graph G = (V, E), a positive integer k and a threshold value thr(v) attached to each vertex v in V . The objective is then to find a subset of k vertices to "activate" such that the number of activated vertices at the end of a propagation process is maximum. A vertex v gets activated if at least thr(v) of its neighbors are. We show that this problem is strongly inapproximable in fpt-time with respect to (w.r.t.) parameter k even for very restrictive thresholds. For unanimity thresholds, we prove that the problem is inapproximable in polynomial time and the decision version is W[1]-hard w.r.t. parameter k. On the positive side, it becomes r(n)-approximable in fpt-time w.r.t. parameter k for any strictly increasing function r. Moreover, we give an fpt-time algorithm to solve the decision version for bounded degree graphs.

02.05.2013 16:15
André Nichterlein
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe