Inhalt des Dokuments
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.
Back to the research colloquium site.