TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 28.06.2012

isti-logo

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.

Date
Speaker
Location
Language
28.06.2012 16:15
Morgan Chopin
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe