6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I do not see how subgraph isomorphism is a special case. Please explain. $\endgroup$ – Austin Buchanan Dec 31 '13 at 3:24
  • $\begingroup$ 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)|$. $\endgroup$ – Austin Buchanan Dec 31 '13 at 3:34
  • $\begingroup$ 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. $\endgroup$ – Yonatan N Dec 31 '13 at 5:59
  • $\begingroup$ 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. $\endgroup$ – vzn Dec 31 '13 at 16:27
  • 1
    $\begingroup$ @SureshVenkat My comment doesn't apply after the question was edited. $\endgroup$ – Austin Buchanan Mar 3 '14 at 18:25
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$?' $\endgroup$ – Sasho Nikolov Dec 31 '13 at 8:17
  • 3
    $\begingroup$ @SashoNikolov The question was edited after my initial response $\endgroup$ – Austin Buchanan Dec 31 '13 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.