edge-connectivity with constraints on number of vertices and removed edges

1
votes

I need to find a subset G' of a graph G that can be disconnected from G by removing some edges. I have some constraints on number of vertices and edges

  1. Number of removed edges should be less than e
  2. Number of vertices in G' should be greater than v

I believe this problem should be a version of minimum-cut max-flow and/or edge-connectivity in graph theory. I wonder if there are already some studies (exact or heuristic alg) investigating this problem?

Any help or suggestions would be really appreciated.

1
graph-theoryconnectivitymax-flow

1 Answers

0
votes

A version of this problem has been studied in the literature as "vertex separator" and "edge separator" problems. There is still room for improvement. The followings are some useful links:

  1. https://www.sciencedirect.com/science/article/pii/002001909290140Q
  2. https://link.springer.com/article/10.1007/s10107-005-0574-7

I hope this helps.