direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

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.

Zusatzinformationen / Extras