<p>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.</p>

<p>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?"</p>

<p>The naive solution:</p>

<pre>
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
</pre>

<p>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.</p>

<p>The problem can be restated as a <a href="http://en.wikipedia.org/wiki/Vertex_cover#Vertex_cover_in_hypergraphs" rel="nofollow">hitting set problem</a> (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)$.</p>

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

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

<p>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.</p>

<p>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, <a href="http://en.wikipedia.org/wiki/K-approximation_of_k-hitting_set" rel="nofollow">an $e_H$-approximation can be computed in polynomial time</a>.  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.</p>

CC BY-SA 3.0
2014-09-02T15:33:46.200Z
2014-09-02T15:33:46.200Z
bbejot
<p>/* My response no longer applies after the question was edited. */</p>

<p>The unweighted versions are trivial.</p>

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

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

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

CC BY-SA 3.0
2013-12-31T08:17:36.567Z
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
CC BY-SA 3.0
2013-12-31T13:53:56.217Z
@SashoNikolov The question was edited after my initial response
Austin Buchanan
CC BY-SA 3.0
2013-12-31T03:54:05.677Z
2013-12-31T13:57:59.047Z
2013-12-31T13:57:59.047Z
Austin Buchanan
<p>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.</p>

<p>Any papers on this problem will be helpful.</p>

CC BY-SA 3.0
2013-12-31T03:24:37.113Z
I do not see how subgraph isomorphism is a special case. Please explain.
Austin Buchanan
CC BY-SA 3.0
2013-12-31T03:34:56.783Z
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](http://en.wikipedia.org/wiki/Null_graph) to be a subgraph of $G$. If you remove vertices from $G$, the answer is $|V(G)|-|V(H)|$.
Austin Buchanan
CC BY-SA 3.0
2013-12-31T05:59:58.580Z
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
CC BY-SA 3.0
2013-12-31T16:27:33.413Z
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
CC BY-SA 3.0
2014-03-03T17:50:37.703Z
@AustinBuchanan I  think the point is that **any** $k$ vertices can be removed from $G$. I don't have an answer to your question about subgraph isomorphism though.
Suresh Venkat
CC BY-SA 3.0
2014-03-03T18:25:03.083Z
@SureshVenkat My comment doesn't apply after the question was edited.
Austin Buchanan
<graph-theory><graph-algorithms><np-hardness><approximation-algorithms>
Edge and vertex fault tolerance in graphs
Arindam Pal
# Edge and vertex fault tolerance in graphs

(Asked by: username_0 on 2013-12-31)

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.

**Tags:** graph-theory, graph-algorithms, np-hardness, approximation-algorithms
> **Comments:**
> **username_1**: I do not see how subgraph isomorphism is a special case. Please explain.  
> **username_1**: 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](http://en.wikipedia.org/wiki/Null_graph) to be a subgraph of $G$. If you remove vertices from $G$, the answer is $|V(G)|-|V(H)|$.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: @AustinBuchanan I  think the point is that **any** $k$ vertices can be removed from $G$. I don't have an answer to your question about subgraph isomorphism though.  
> **username_1**: @SureshVenkat My comment doesn't apply after the question was edited.  

---

## 2 answers

### Answer by username_5 on 2014-09-02. Score: 3

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 by username_1 on 2013-12-31. Score: 0

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

> **Comments:**
> **username_6**: 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$?'  
> **username_1**: @SashoNikolov The question was edited after my initial response  

---

