### 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.

Date | Speaker | Location | Language |
---|---|---|---|

02.05.2013 16:15 | André Nichterlein | TEL 512 | english/german |