Edge and vertex fault tolerance in graphs

Question

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.

Answer 1

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.

Answer 2

/* My response no longer applies after the question was edited. */

The unweighted versions are trivial.

The answer to "How many vertices can be removed so that $H$ is still a subgraph?" is $|V(G)|-|V(H)|$.

The answer to "How many edges can be removed so that $H$ is still a subgraph" is $|E(G)|-|E(H)|$.

The complexity may be different when the graphs are weighted or if you don't assume a priori that $H \subseteq G$.