Edge and vertex fault tolerance in graphs Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What about the same question when edges are replaced by vertices? A generalization is to consider weights on edges/vertices and ask for maximum weight edges/vertices. I want both a bound as well as an algorithm. This problem is NP-hard as subgraph isomorphism is a special case of it.

Any papers on this problem will be helpful.
The question is very general and so the following is only a partial solution.  My main motivation was to draw the connection between this and k-hitting sets.

As Arindam has pointed out, this problem (or the decision version thereof) could be used to solve the subgraph isomorphism problem: "Is $H$ a subgraph of $G$ if any $0$ edges of $G$ are removed?".  But as is often the case, we still want to know "is it possible to do better than the naive solution?"

The naive solution:


for i in 0 ... (|E(G)|-|E(H)|+1)
    for every i-subset of edges, S, in E(G)
        if H is not a subgraph of (G - S)
            return k=i-1 as the greatest number of edges that can be removed


Ignoring the obvious edge cases (returning $-1$ when $H$ is not a subgraph of $G$) then the cost is basically $\sum_{i=0}^k \binom{|E(G)|}{i}$ computations of he subgraph isomorphism problem on inputs (basically) $G$ and $H$.  And so, we are basically up against a possibly exponential number of subgraph isomorphism problems.

The problem can be restated as a hitting set problem (also known as a vertex cover of a hypergraph problem).  Let $S$ be the set of all sets, $T$, where $T$ is a set of $|E(H)|$ edges of $G$, and $H$ is isomorphic to $G - (E(G) - T)$.

Note, $S$ is not every mapping of $H$ onto $G$, but is every edge set that can be mapped to.

Let $h$ be the size of the minimum hitting set of $S$.  Then $k=h-1$.

This is neat, but it is not immediately useful.  Calculating a minimum hitting set is NP-hard, and the input into the problem is possibly exponential in the size of the input of our original problem.  Double-wam-o.

However, it does provide us with a case for a fast approximation.  If $|E(H)|$ is small (and by that I mean bounded by some constant $e_H$), then we have $|S| = O(\binom{|E(G)|}{e_H})$.  Also, an $e_H$-approximation can be computed in polynomial time.  Thus the real work is in finding $S$, which can be done with $\binom{E(G)}{e_H}$ cases of the graph isomorphism problem.  The naive solution does not compute in polynomial time when $E(H)$ is bound because $k$ is not bound.