According to wikipedia, if your only constraint is minimizing the number of edges removes, it's easy. Now whether those algorithms are approriate for solving your problem as stated exactly or approximately, thats another question entirely. I'd guess that it's certainly easy (in at least one of an exact or approximate sense) as long as the graphs have some nice sparseness or geometric structure such as being planar or k regular.
No comments:
Post a Comment