That's what I'm doing now, but the results aren't great. If there's a way to estimate a lower bound on the number of edges to remove, I can figure out if the results aren't great because of the approximation, or because of the nature of the graph...