Randomly removing n edges without disconnecting graph

Question

I'm using the igraph package in R. I have a connected graph G=(V,E), how can I randomly remove some edges (say, n < |E|) but without disconnecting the given graph. In other words, I mustn't remove any bridges. Any hints on how that could be done?

Answer 1

A simple approach would be to keep randomly selecting and removing sets of n nodes until you found a set that doesn't increase the number of components of the graph:

remove.edges <- function(g, n) {
  num.tries <- 0
  while (TRUE) {
    num.tries <- num.tries + 1
    g2 <- delete.edges(g, E(g)[sample(seq_along(E(g)), n)])
    if (no.clusters(g2) == no.clusters(g)) {
      print(paste("Total number of tries:", num.tries))
      return(g2)
    }
  }
}

Let's try it out with a sample graph:

library(igraph)
set.seed(144)
g <- erdos.renyi.game(10, 0.4)
g2 <- remove.edges(g, 5)
# [1] "Total number of tries: 3"

This could be terribly inefficient for a large, sparse graph coupled with a large n value. In that case, you'll probably want to run something like Tarjan's Bridge-Finding Algorithm at each iteration and limit your random selections to not be bridges. Unfortunately, I can't find an implementation of that algorithm in R, so you'd probably need to do some implementation to get that to work.

Answer 2

A simple technique is to find a cycle in the graph and remove an edge from this cycle. To find a cycle I would do a depth first search until you find a node you have previously seen on the search.

For example, if you are at node x while performing the DFS and you discover a node y in x's neighborhood, then if x also already exists in the DFS tree, you have found a cycle. At this point you can safely remove any edge on this cycle without risk of it being a bridge. This should run pretty quickly if the graph isn't very sparse.

Note that in practice this DFS technique will often just resemble a random walk around the graph until encountering a previously seen node.