  Consider a dynamic network and a given distributed problem. At any point in
time, there might exist several solutions that are equally good with respect to
the problem specification, but that are different from an algorithmic
perspective, because some could be easier to update than others when the
network changes. In other words, one would prefer to have a solution that is
more robust to topological changes in the network; and in this direction the
best scenario would be that the solution remains correct despite the dynamic of
the network.
  In~\cite{CasteigtsDPR20}, the authors introduced a very strong robustness
criterion: they required that for any removal of edges that maintain the
network connected, the solution remains valid. They focus on the maximal
independent set problem, and their approach consists in characterizing the
graphs in which there exists a robust solution (the existential problem), or
even stronger, where any solution is robust (the universal problem). As the
robustness criteria is very demanding, few graphs have a robust solution, and
even fewer are such that all of their solutions are robust. In this paper, we
ask the following question: \textit{Can we have robustness for a larger class
of networks, if we bound the number $k$ of edge removals allowed}? (See the
full paper for the full abstract.)

Data Structures and Algorithms