TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 28.06.2012


Page Content

to Navigation

The Robust Set Problem: Parameterized Complexity and Approximation

Morgan Chopin (Ph.D student, Université Paris-Dauphine)

We introduce the k-Robust Set problem: given a graph G=(V,E), a threshold function t, and an integer k, find a subset of vertices V' of size at least k such that every vertex v in G has less than t(v) neighbors in V'. This problem occurs in the context of the spread of undesirable agents through a network (virus, ideas, fire, . . .). Informally speaking, the problem asks to find the largest subset of vertices with the property that if anything bad happens in it then this will have no consequences on the remaining graph. The threshold t(v) of a vertex v represents its reliability regarding its neighborhood; that is, how many neighbors can be infected before v gets himself infected.

We present some results we got about the parameterized complexity of k-Robust Set and the approximation of the associated maximization problem.

28.06.2012 16:15
Morgan Chopin
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe