# 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.

• I do not see how subgraph isomorphism is a special case. Please explain. – Austin Buchanan Dec 31 '13 at 3:24
• From which graph are you removing edges/vertices? In either case, the answer to "How many vertices can be removed so that $H$ is still a subgraph?" is trivial. If you remove vertices from $H$, the answer is either $|V(H)|$ or $|V(H)|-1$ depending on whether you consider the null graph to be a subgraph of $G$. If you remove vertices from $G$, the answer is $|V(G)|-|V(H)|$. – Austin Buchanan Dec 31 '13 at 3:34
• The weighted version of the problem is not quite as trivial. However, setting all weights within a graph $G$ to (near) zero and augmenting it with a disjoint clique $C$ of size $x$ with large weights, one can test if $G$ contains an $k$-clique by testing if one can remove a nontrivially-weighted subgraph of the newly constructed graph and still maintain a $k$-clique (i.e. removing $C$ maintains the "contains $k$-clique property", meaning $G$ had a $k$-clique in the first place). This also shows that any multiplicative approximation algorithm is also out of the question. – Yonatan N Dec 31 '13 at 5:59
• there are some various nontrivial versions/concepts of "fault tolerance" of graphs often measured in whether connectivity between all vertices is maintained/possible via alternate paths after loss of edges. this is a key concept behind internet router connections. – vzn Dec 31 '13 at 16:27
• @SureshVenkat My comment doesn't apply after the question was edited. – Austin Buchanan Mar 3 '14 at 18:25

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.

/* 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$.

• The way I read the question, you got the quantifiers wrong. The question is, 'what is the maximum $k$, s.t. if any $k$ edges are removed from $G$, then $H$ is still a subgraph?' I think you are answering 'what is the maximum $k$, s.t. there exists a choice of $k$ edges to remove and still have $H$ be a subgraph of $G$?' – Sasho Nikolov Dec 31 '13 at 8:17
• @SashoNikolov The question was edited after my initial response – Austin Buchanan Dec 31 '13 at 13:53