  The study of fault-tolerant data structures for various network design
problems is a prominent area of research in computer science. Likewise, the
study of NP-Complete problems lies at the heart of computer science with
numerous results in algorithms and complexity. In this paper we raise the
question of computing fault tolerant solutions to NP-Complete problems; that is
computing a solution that can survive the "failure" of a few constituent
elements. This notion has appeared in a variety of theoretical and practical
settings such as estimating network reliability, kernelization (aka instance
compression), approximation algorithms and so on. In this paper, we seek to
highlight these questions for further research.
  As a concrete example, we study the fault-tolerant version of the classical
Feedback Vertex Set (FVS) problem, that we call Fault Tolerant Feedback Vertex
Set (FT-FVS). Recall that, in FVS the input is a graph $G$ and the objective is
to compute a minimum subset of vertices $S$ such that $G-S$ is a forest. In
FT-FVS, the objective is to compute a minimum subset $S$ of vertices such that
$G - (S \setminus \{v\})$ is a forest for any $v \in V(G)$. Here the vertex $v$
denotes a single vertex fault. We show that this problem is NP-Complete, and
then present a constant factor approximation algorithm as well as an
FPT-algorithm parameterized by the solution size. We believe that the question
of computing fault tolerant solutions to various NP-Complete problems is an
interesting direction for future research.
